Er der problemer i PSPACE, som der ikke er nogen kendt NP-algoritme for?
I området for beregningsmæssig kompleksitetsteori, især når man undersøger rumkompleksitetsklasser, er forholdet mellem PSPACE og NP af væsentlig interesse. For at besvare spørgsmålet direkte: ja, der er problemer i PSPACE, som der ikke er nogen kendt NP-algoritme til. Denne påstand er forankret i definitionerne og relationerne mellem disse kompleksitetsklasser.
PSPACE er klassen af beslutningsproblemer, der kan løses af en Turing-maskine ved hjælp af en polynomisk mængde plads. Med andre ord er et problem i PSPACE, hvis der findes en algoritme, der kan løse det ved at bruge en mængde hukommelse, der er polynomisk i størrelsen af input. Denne klasse omfatter en bred vifte af problemer, hvoraf nogle er ret komplekse og involverer indviklede beregningsprocesser.
NP er på den anden side klassen af beslutningsproblemer, for hvilke en foreslået løsning kan verificeres i polynomiel tid af en deterministisk Turing-maskine. Dette betyder, at hvis nogen giver dig en kandidatløsning til et problem i NP, kan du hurtigt kontrollere rigtigheden af den løsning, specifikt i polynomisk tid i forhold til inputstørrelsen.
Forholdet mellem disse to klasser er sådan, at NP er en delmængde af PSPACE. Dette skyldes, at ethvert problem, der kan verificeres i polynomisk tid, også kan løses i polynomium. For at forstå hvorfor, overvej, at en polynomial-time verifikator kun kan læse et polynomielt antal bits af input og den foreslåede løsning. Derfor kan det simuleres af en polynomium-rummaskine, som holder styr på de positioner, den har læst, og de operationer, den har udført.
Det modsatte vides dog ikke at være sandt; det vil sige, at det ikke vides, om PSPACE er en delmængde af NP. Faktisk er det en udbredt opfattelse, at PSPACE indeholder problemer, der ikke er i NP, selvom dette ikke er blevet formelt bevist. Denne tro er baseret på eksistensen af problemer i PSPACE, der synes at kræve mere end polynomiel tid at løse, selvom de kan løses med polynomium.
Et af de kanoniske eksempler på et problem i PSPACE, som ikke vides at være i NP, er problemet med Quantified Boolean Formula (QBF). QBF er en generalisering af det boolske tilfredshedsproblem (SAT), som er NP-komplet. Mens SAT spørger, om der findes en tildeling af sandhedsværdier til variabler, der gør en given boolsk formel sand, involverer QBF indlejrede kvantifikatorer over variablerne, såsom "for alle x eksisterer der sådan, at formlen er sand." Tilstedeværelsen af disse kvantifikatorer gør QBF betydeligt mere kompleks. QBF er PSPACE-komplet, hvilket betyder, at det er lige så svært som ethvert problem i PSPACE. Hvis der var en NP-algoritme for QBF, ville det indebære, at NP er lig med PSPACE, et resultat, der ville være banebrydende og generelt anses for usandsynligt.
Et andet illustrativt eksempel er problemet med at bestemme vinderen i generaliserede spil, såsom generaliserede versioner af skak eller Go, spillet på et N x N-bræt. Disse problemer involverer et potentielt eksponentielt antal træk og konfigurationer, men de kan afgøres ved hjælp af polynomisk rum ved at udforske alle mulige spiltilstande systematisk. Disse problemer er også PSPACE-komplette, hvilket yderligere tyder på, at der findes problemer i PSPACE, som ikke er i NP.
For at dykke dybere ned i, hvorfor visse problemer i PSPACE menes at være uden for NP, skal du overveje arten af rumgrænsede versus tidsbegrænsede beregninger. Polynomisk rum giver mulighed for et potentielt eksponentielt antal beregningstrin, så længe det anvendte rum forbliver polynomielt afgrænset. Dette står i skarp kontrast til NP, hvor tiden er polynomisk afgrænset. Den eksponentielle tid, der tillades af polynomisk rum, kan bruges til at løse problemer, der involverer udtømmende søgninger over eksponentielt store rum, såsom dem, man støder på i QBF og generaliserede spil.
Desuden er der indviklede teoretiske konstruktioner, der yderligere understøtter sondringen mellem PSPACE og NP. For eksempel generaliserer begrebet alternering, introduceret af Chandra, Kozen og Stockmeyer, ikke-determinisme og fører til klassen AP (alternerende polynomisk tid). Det er blevet vist, at AP er lig med PSPACE, hvilket giver et andet perspektiv på styrken af polynomiske rumberegninger. Veksling involverer en sekvens af eksistentielle og universelle kvantificeringsmidler, der afspejler strukturen af QBF, og viser kompleksiteten, der ligger i PSPACE-problemer.
Det er også værd at bemærke, at adskillelsen af kompleksitetsklasser er et grundlæggende åbent spørgsmål i teoretisk datalogi. Det berømte P vs NP-problem er et særligt tilfælde af denne bredere undersøgelse. På samme måde forbliver spørgsmålet om, hvorvidt NP er lig med PSPACE, uløst. Men konsensus på området, baseret på omfattende undersøgelser og arten af kendte problemer, er, at PSPACE sandsynligvis indeholder problemer, der ikke er i NP.
Eksistensen af problemer i PSPACE, for hvilke der ikke er nogen kendt NP-algoritme, understøttes af definitionerne og relationerne mellem disse kompleksitetsklasser, såvel som af konkrete eksempler som QBF og generaliserede spilproblemer. Disse eksempler fremhæver de indviklede og potentielt eksponentielle beregningsprocesser, der kan styres inden for polynomisk rum, men som næppe er begrænset til polynomiel tid, hvilket placerer dem uden for NP's område.
Andre seneste spørgsmål og svar vedr Kompleksitet:
- Er PSPACE-klassen ikke lig med EXPSPACE-klassen?
- Er P kompleksitetsklassen en delmængde af PSPACE-klassen?
- Kan vi bevise, at Np- og P-klassen er ens ved at finde en effektiv polynomielløsning for ethvert NP-fuldt problem på en deterministisk TM?
- Kan NP-klassen være lig med EXPTIME-klassen?
- Kan et SAT-problem være et komplet NP-problem?
- Kan et problem være i NP-kompleksitetsklassen, hvis der er en ikke-deterministisk turingmaskine, der løser det i polynomisk tid
- NP er klassen af sprog, der har polynomielle tidsverifikatorer
- Er P og NP faktisk den samme kompleksitetsklasse?
- Er enhver kontekst frit sprog i P-kompleksitetsklassen?
- Er der en modsætning mellem definitionen af NP som en klasse af beslutningsproblemer med polynomial-tids-verifikatorer og det faktum, at problemer i klassen P også har polynomial-time-verifikatorer?
Se flere spørgsmål og svar i Complexity