|
|
(не показана 1 промежуточная версия 1 участника) |
Строка 1: |
Строка 1: |
− | Класс задач, разрешимых на [[Машина Тьюринга|машине Тьюринга]], причем существует алгоритм ([[машина Тьюринга]]), использующий память не более чем полиномиального размера от длины входа.
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
− | | + | |
− | Более формально, через определение класса [[DSPACE]]:
| + | |
− | | + | |
− | <amsmath>{\cal PSPACE} \equiv \cup_{c>0} {\cal DSPACE}(n^c)</amsmath>
| + | |
− | | + | |
− | [[Category:Классы сложности]]
| + | |
− | {{replicate-from-custiswiki-to-lib}}
| + | |