P-komplett

I beräkningskomplexitetsteori är ett beslutsproblem P-komplett ( komplett för komplexitetsklassen P ) om det är i P och varje problem i P kan reduceras till det genom en lämplig reduktion.

Begreppet P-fullständiga beslutsproblem är användbart i analysen av:

• vilka problem som är svåra att parallellkoppla effektivt,
• vilka problem är svåra att lösa på begränsat utrymme.

särskilt när starkare föreställningar om reducerbarhet än polytime-reducerbarhet övervägs.

Den specifika typen av reduktion som används varierar och kan påverka den exakta uppsättningen av problem. Generellt används reduktioner starkare än polynomtidsreduktioner, eftersom alla språk i P (förutom det tomma språket och språket för alla strängar) är P -kompletta under polynomtidsreduktioner. Om vi ​​använder NC- reduktioner, det vill säga reduktioner som kan arbeta i polylogaritmisk tid på en parallell dator med ett polynomantal processorer, så ligger alla P -kompletta problem utanför NC och kan därför inte effektivt parallelliseras, under det obevisade antagandet att NC ≠ P . Om vi ​​använder den starkare log-space-reduktionen förblir detta sant, men dessutom lär vi oss att alla P -kompletta problem ligger utanför L under det svagare obevisade antagandet att L ≠ P . I det senare fallet kan mängden P -komplett vara mindre.

Motivering

Klassen P , typiskt sett bestå av alla "lösbara" problem för en sekventiell dator, innehåller klassen NC , som består av de problem som effektivt kan lösas på en parallell dator. Detta beror på att parallella datorer kan simuleras på en sekventiell maskin. Det är inte känt om NC = P . Det är med andra ord inte känt om det finns några lösta problem som till sin natur är sekventiella. Precis som det är allmänt misstänkt att P inte är lika med NP , så är det allmänt misstänkt att NC inte är lika med P.

På samma sätt innehåller klassen L alla problem som kan lösas av en sekventiell dator i logaritmiskt utrymme. Sådana maskiner körs i polynomtid eftersom de kan ha ett polynomantal konfigurationer. Det misstänks att L ≠ P ; det vill säga att vissa problem som kan lösas i polynomtid också kräver mer än logaritmiskt utrymme.

På samma sätt som användningen av NP-kompletta problem för att analysera P = NP- frågan, tjänar P -komplettproblemen, ses som de "troligen inte parallelliserbara" eller "troligen inneboende sekventiella" problemen, på ett liknande sätt för att studera NC = P fråga. Att hitta ett effektivt sätt att parallellisera lösningen till något P -komplett problem skulle visa att NC = P . Det kan också ses som "problemen som kräver superlogaritmiskt utrymme"; en log-space-lösning på ett P -komplett problem (med definitionen baserad på log-space-reduktioner) skulle innebära L = P .

Logiken bakom detta är analog med logiken att en polynom-tidslösning av ett NP -komplett problem skulle bevisa P = NP : om vi har en NC- reduktion från vilket problem som helst i P till ett problem A, och en NC -lösning för A, då NC = P . På liknande sätt, om vi har en log-space-reduktion från vilket problem som helst i P till ett problem A, och en log-space-lösning för A, då L = P .

P-kompletta problem

Det mest grundläggande P -kompletta problemet under logspace många-ett-reduktioner är följande: givet en Turing-maskin $M$ , en ingång för den maskinen x och ett tal T (skrivet i unary ), $\langle M,x,T\rangle$ stannar maskinen på den ingången inom de första T- stegen? För valfritt x i $L$ i P, mata ut kodningen för Turing-maskinen som accepterar den i polynomtid, kodningen av x själv och ett antal steg $T=p(|x|)$ motsvarande p som där är polynom-tid bunden på driften av Turing-maskinen $M_{L}$ som bestämmer $L$ , $\langle M,x,p(|x|)\rangle$ . Maskinen M stannar på x inom $p(|x|)$ steg om och endast om x är i L. Klart, om vi kan parallellisera en allmän simulering av en sekventiell dator (dvs. Turingmaskinsimulering av en Turingmaskin), då kommer vi att kunna parallellisera vilket program som helst som körs på den datorn. Om det här problemet finns i NC , så är det även alla andra problem i P. Om antalet steg skrivs i binärt är problemet EXPTIME-komplett . Detta problem illustrerar ett vanligt knep i teorin om P -fullständighet. Vi är egentligen inte intresserade av om ett problem kan lösas snabbt på en parallell maskin. Vi är bara intresserade av om en parallellmaskin löser det mycket snabbare än en sekventiell maskin. Därför måste vi omformulera problemet så att den sekventiella versionen är i P . Det är därför detta problem krävde T skrevs i unary. Om ett tal T skrivs som ett binärt tal (en sträng med n ettor och nollor, där n = log T ), så kan den uppenbara sekventiella algoritmen ta tiden 2 ⁿ . Å andra sidan, om T skrivs som ett unärt tal (en sträng av n ettor, där n = T ), så tar det bara tid n . Genom att skriva T i unär snarare än binärt har vi reducerat den uppenbara sekventiella algoritmen från exponentiell tid till linjär tid. Det sätter det sekventiella problemet i P . Sedan kommer det att vara i NC om och bara om det är parallelliserbart.

Många andra problem har visat sig vara P -kompletta, och därför anses allmänt vara sekventiella. Dessa inkluderar följande problem som är P -kompletta under åtminstone loggutrymmesreduktioner, antingen som givna eller i en beslutsproblemform:

• Kretsvärdeproblem (CVP) – Givet en krets beräknar ingångarna till kretsen och en grind i kretsen utsignalen från den grinden.
• Begränsat fall av CVP – Precis som CVP, förutom att varje grind har två ingångar och två utgångar (F och inte F), är vartannat lager bara OCH-grindar, resten är ELLER-grindar (eller, på motsvarande sätt, alla grindar är NAND-grindar, eller alla grindar är NOR-grindar), kommer ingångarna till en grind från det omedelbart föregående lagret
• Linjär programmering – Maximera en linjär funktion som är föremål för linjära ojämlikhetsbegränsningar
• Lexikografiskt första djupet första sökningsordning – Givet en graf med fast ordnade närliggande listor och noder u och v , besöks vertex u före vertex v i en djup-första sökning inducerad av ordningen på närliggande listor?
• Kontext gratis grammatikmedlemskap – Med tanke på en sammanhangsfri grammatik och en sträng, kan den strängen genereras av den grammatiken?
• Horn-tillfredsställelse – givet en uppsättning Horn-satser , finns det en variabeltilldelning som uppfyller dem? Detta är P: s version av det booleska tillfredsställbarhetsproblemet .
• Game of Life – Givet en initial konfiguration av Conways Game of Life , en viss cell och en tid T (i unary), lever den cellen efter T -steg?
• LZW (algoritm) (1978 paradigm) Datakomprimering – givna strängar s och t , kommer komprimering av s med en LZ78-metod att lägga till t till ordboken? (Observera att för LZ77 -komprimering som gzip är detta mycket enklare, eftersom problemet minskar till "Is t in s ?".)
• Typinferens för partiella typer – Med tanke på en otypad term från lambdakalkylen , avgör om denna term har en partiell typ.

De flesta av språken ovan är P -kompletta under ännu starkare föreställningar om reduktion, såsom enhetliga $AC^{0}$ många-en-reduktioner, DLOGTIME-reduktioner eller polylogaritmiska projektioner.

För att bevisa att ett givet problem i P är P -komplett, försöker man typiskt reducera ett känt P -komplett problem till det givna.

År 1999 visade Jin-Yi Cai och D. Sivakumar, som bygger på arbete av Ogihara, att om det finns ett gles språk som är P -komplett, så är L = P .

P -kompletta problem kan vara lösbara med olika tidskomplexiteter . Till exempel kretsvärdeproblemet lösas i linjär tid genom en topologisk sortering . Eftersom reduktionerna till ett P -fullständigt problem kan ha olika tidskomplexitet, innebär detta faktum naturligtvis inte att alla problem i P också kan lösas i linjär tid.

Problem som inte är kända för att vara P-kompletta

Vissa NP -problem är inte kända för att vara antingen NP -kompletta eller i P . Dessa problem (t.ex. factoring , grafisomorfism , paritetsspel ) misstänks vara svåra . På liknande sätt finns det problem i P som inte är kända för att vara vare sig P -komplett eller NC , men som anses vara svåra att parallellisera. Exempel inkluderar beslutsproblemformerna att hitta den största gemensamma delaren för två tal, bestämma vilket svar den utökade euklidiska algoritmen skulle returnera när den ges två tal, och beräkna maximal viktmatchning av en graf med stora heltalsvikter.

Anteckningar

•   Greenlaw, Raymond, James Hoover och Walter Ruzzo. 1995. Limits To Parallel Computation; P-Fullständighetsteori . ISBN 0-19-508591-4 . — Utvecklar teorin och katalogiserar sedan 96 P-Complete problem.
• Satoru Miyano, Shuji Shiraishi och Takayoshi Shoudai. En lista över P-Complete-problem . Kyushu University, RIFIS-TR-CS-17. december 1990.