P (kompleksitet)

Klasse P , også noen ganger bemerket PTIME eller DTIME (n O (1) ), er en veldig viktig klasse av kompleksitetsteori , et felt med teoretisk informatikk og matematikk . Per definisjon er et beslutningsproblem i P hvis det avgjøres av en deterministisk Turing-maskin i polynomisk tid med hensyn til størrelsen på inngangen. Vi sier at problemet avgjøres i polynomisk tid .

Problemene i P betraktes som "gjennomførbare" ( gjennomførbare på engelsk), enkle å løse (i den forstand at det kan gjøres relativt raskt). Dette er Cobhams avhandling utgitt av den amerikanske forskeren Alan Cobham. René Lalement tilskriver denne oppgaven til Cook. Klasse P er inkludert i klasse NP , noe som fører til et av de store åpne problemene med kompleksitetsteori, nemlig: Er P lik NP?

Eksempler på problemer i P

Et problem er i P hvis det er en algoritme som bestemmer det i polynomisk tid. La oss sitere:

2SAT restriksjoner og HORNSAT SAT problem er i P .
Tilkoblingsmuligheter i en graf: Et eksempel på et polynomproblem er tilkoblingsmuligheter i en graf. Gitt en graf med n hjørner (vi anser at størrelsen på dataene, derfor av grafen, er antall hjørner), er det et spørsmål om å vite om alle parene i hjørnene er forbundet med en bane. En grundig traversalgoritme bygger et tre som strekker seg over grafen fra et toppunkt. Hvis dette treet inneholder alle hjørnene i grafen, er grafen koblet sammen. Tiden det tar å bygge dette treet er høyst c . n ² (hvor c er en konstant og n er antall hjørner av diagrammet), så problemet er i klassen P .

Noen ganger har beviset på medlemskap i P , som vanligvis gjøres ved oppdagelsen av en polynomalgoritme, tatt mange års forskning:

Den AKS primality testen er en algoritme som viser at problemet med hvorvidt et heltall er primtall eller ikke kan løses ved hjelp av en polynomisk algoritme.

Linear Programming: Den algoritmer indre punkt brukes til å klassifisere den lineære optimaliserings i klassen P . Dette problemet er til og med P -komplett .

Formelle definisjoner

Klassisk definisjon ved bruk av Turing-maskiner

Vi betegner ved TID ( t ( n )) klassen av beslutningsproblemer som kan avgjøres i tid av størrelsesorden av t ( n ) på en deterministisk maskin (hvor n er størrelsen på inngangen). Så per definisjon

{\ mathrm {P}} = \ bigcup _ {{c> 1}} {\ mathrm {TIME}} (n ^ {c}).

Definisjon med kretser

P kan også defineres ved hjelp av ensartede familier av boolske kretser . Et språk L er i P hvis, og bare hvis det eksisterer en familie av boolske kretser , ensartet i polynomisk tid (dvs. det eksisterer en deterministisk Turing-maskin som produserer på inngangen 1 n ) slik som ${\ displaystyle \ {C_ {n}: n \ i \ mathbb {N} \}}$ $C_ {n}$

for alt , ta n input bits og returner en output bit $n \ in \ mathbb {N}$ $C_ {n}$
For alle x i L , ${\ displaystyle C_ {| x |} (x) = 1}$
For alle x som ikke er i L , ${\ displaystyle C_ {| x |} (x) = 0}$

Definisjonen av kretser kan svekkes ved å bruke en ensartet familie i logaritmerommet og gir alltid en tilsvarende definisjon for klassen P. Hvis vi slapper av antagelsen om ensartethet, definerer vi klassen P / poly .

Forhold til andre klasser

Vi har den åpenbare inkluderingen P NP , men et av de store åpne spørsmålene innen teoretisk informatikk er problemet P = NP? . $\ scriptstyle \ subseteq$

Vi kan plassere P i språkhierarkiet, klassifisert i henhold til det nødvendige rommet: det inneholder NL (klassen av problemer som kan løses på en ikke-deterministisk maskin i logaritmisk rom) og er inneholdt av PSPACE (klassen av problemer som kan løses på en ikke-deterministisk maskin i logaritmisk rom). løses i polynomisk rom). Inkluderingene er som følger (vi vet ikke om de er strenge):

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE P ≠ EXPTIME (i henhold til det deterministiske tidshierarki- teoremet )

Videre er P det første nivået i polynomhierarkiet . Og P er inkludert i polynomklassene på kraftigere maskiner (kvante eller for eksempel bruk av sjanse), som ZPP , BPP og BQP .

P-komplette problemer

Et avgjørelsesproblem A sies å være P - komplett , eller fullstendig for klasse P , hvis det er i klasse P og hvis noe problem av klasse P kan reduseres til A i logaritmisk rom (dvs. at oversettelsen fra en forekomst x av problemet til en forekomst av A kan gjøres ved å bruke et mellomrom O (log | x |)). Følgende problemer er P- komplette .

Horn-lø: den SAT problemet vanligvis er NP-komplette , men dens begrensning setter Horn bestemmelser er i P . Det er P-komplett.
Problem med evaluering av en krets : Dette problemet, på engelsk circuit value problem (CVP), består i å bestemme om resultatet for funksjonen som utføres på en gitt inngang for en gitt boolsk krets tilsvarer en gitt verdi.
Problemet med å vite om språket betegnet med en algebraisk grammatikk er tomt eller ikke.
Bestem om språket til en algebraisk grammatikk er uendelig.
Problemet med modellkontroll ( modellkontroll engelsk) en form for tidslogisk CTL er i P og har blitt bevist P-komplett. Mer presist viser beviset at modellkontrollen av en formel for det syntaktiske fragmentet av CTL med operatorene AX (for enhver etterfølger) og EX (det er en etterfølger) er P-vanskelig. Dermed er modellkontrollen av en formel for modalogikk K P-komplett.
Det problemet med maksimal flyt og dermed reell lineær programmering .

Hvis det er et hult språk som er P-komplett, så er P = LOGSPACE .

Ytterligere egenskaper

I noen tilfeller snakker vi om sterkt eller svakt polynomiske tidsalgoritmer . Dette skillet eksisterer for problemer hvis oppføring inneholder heltall. Vi snakker om svakt polynomisk tid hvis heltallene må gis i unary skrift (dvs. tallet n teller som en størrelse n ) for å ha en polynomtid, og vi snakker om sterkt polynomisk tid hvis selv den kompakte skrivingen ( n har størrelseslogg n )) gir polynomskompleksitet.

Se også

NP-klasse

P / poly

Bibliografi

(en) Sanjeev Arora og Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 1 ("Beregningsmodellen - og hvorfor det ikke betyr noe")

Ekstern lenke

(no) P-klassen i Complexity Zoo

Merknader og referanser

(in) Sanjeev Arora og Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 1 i de historiske notatene.
Alan Cobham, " The intrinsic computational vanskeligheten av funksjoner ", Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science , North Holland,1965.
René Lalement, logisk reduksjonsoppløsning , Masson, s. 344
Richard E. Ladner , “ Kretsverdiproblemet er loggplass komplett for P, ” ACM SIGACT News , vol. 7, n o 1,1 st januar 1975, s. 18–20 ( ISSN 0163-5700 , DOI 10.1145 / 990518.990519 , lest online , åpnet 30. oktober 2018 )
" Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak " , på theory.cs.princeton.edu (åpnet 30. oktober 2018 ) , s. 119, Th 6.30
Neil D. Jones og William T. Laaser , “ Komplette problemer for deterministisk polynomisk tid, ” Theor. Beregn. Sci. , vol. 3, n o 1,1976, s. 105-117.
" math.stackexchange.com "
André Arnold og Paul Crubille , “ En lineær algoritme for å løse faste punktligninger på overgangssystemer ”, Inf. Prosess. Lett. , vol. 29, n o toSeptember 1988, s. 57–66 ( ISSN 0020-0190 , DOI 10.1016 / 0020-0190 (88) 90029-4 , leses online , åpnes 27. februar 2019 )
EM Clarke , EA Emerson og AP Sistla , “ Automatic Verifikasjon av Finite-state Samtidige Systems Bruke Oral Logic Spesifikasjoner ”, ACM Trans. Program. Lang. Syst. , vol. 8, n o toApril 1986, s. 244–263 ( ISSN 0164-0925 , DOI 10.1145 / 5397.5399 , lest online , åpnet 27. februar 2019 )
Philippe Schnoebelen , The Complexity of Temporal Logic Model Checking ,1 st januar 2002( les online ).
(in) " Maksimum strømningsproblem er loggplass for full P " , Teoretisk informatikk , vol. 21, n o 1,1 st oktober 1982, s. 105–111 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (82) 90092-5 , lest online , åpnet 8. november 2018 )
Jin-Yi Cai og D. Sivakumar , “ Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis, ” Journal of Computer and System Sciences , vol. 58, n o to1 st april 1999, s. 280–296 ( ISSN 0022-0000 , DOI 10.1006 / jcss.1998.1615 , lest online , åpnet 14. juli 2019 )