Clasa PSPACE

Clasa de complexitate PSPACE  este setul tuturor problemelor de solubilitate din teoria complexității computaționale care pot fi rezolvate de o mașină Turing cu o constrângere de spațiu polinomial .

Mașină Turing cu constrângere de spațiu polinomial

Dacă este adevărat pentru o anumită mașină Turing că există un polinom p ( n ) astfel încât, pe orice intrare de dimensiune n , acesta va vizita cel mult p ( n ) celule, atunci o astfel de mașină se numește o mașină Turing cu o constrângere de spațiu polinomial .

Se poate arăta că:

1. Dacă o mașină Turing cu spațiu delimitat polinom de p ( n ) , atunci există o constantă c pentru care această mașină își admite intrarea de lungime n în cel mult pași.

Rezultă că toate limbajele de mașină Turing cu constrângeri de spațiu polinomial sunt recursive .

Clasele PSPACE, NPSPACE

Clasa de limbaj PSPACE  este setul de limbaje permise de o mașină Turing deterministă cu o constrângere de spațiu polinomial.

Clasa de limbaj NPSPACE  este setul de limbaje permis de o mașină Turing nedeterministă cu o constrângere de spațiu polinomial.

Următoarele afirmații sunt adevărate pentru clasele de limbă PSPACE și NPSPACE:

1. PSPACE = NPSPACE (acest fapt este demonstrat de teorema lui Savitch )

2. Limbile sensibile la context sunt un subset al PSPACE

3.

patru.

5. Dacă limbajul aparține PSPACE, atunci există o mașină Turing cu o constrângere de spațiu polinomial astfel încât să se oprească în pași pentru unele c și un polinom p ( n ) .

Se știe că cel puțin unul dintre cele trei simboluri de includere în enunț trebuie să fie strict (adică să excludă egalitatea mulțimilor, relația dintre care descrie), dar nu se știe care dintre ele. De asemenea, cel puțin un subset dintr-o declarație trebuie să fie propriu (adică cel puțin un caracter de includere trebuie să fie strict). Există o presupunere că toate aceste incluziuni sunt stricte .

PSPACE-Provocare completă

O problemă PSPACE-completă  este o problemăconform lui Karppot fitimp polinomial.

Următoarele fapte sunt cunoscute despre problema PSPACE-complete:

Dacă este o problemă completă PSPACE, atunci

unu.

2.

Un exemplu de problemă PSPACE-completă: găsirea de formule booleene adevărate cu cuantificatori .

Literatură

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .

• Hopcroft, Motwani, Ullman: „Introducere în teoria automatelor, limbaje și calcul”