P (złożoność) - P (complexity)

W teorii złożoności obliczeniowej , P , znane także jako PTIME lub DTIME ( n ^{O (1)} ), jest podstawowym klasa złożoności . Zawiera wszystkie problemy decyzyjne, które mogą być rozwiązane przez deterministyczną maszynę Turinga przy użyciu wielomianowej ilości czasu obliczeń lub czasu wielomianowego .

Teza Cobhama głosi, że P jest klasą problemów obliczeniowych, które są „efektywnie rozwiązywalne” lub „ wykonalne ”. To jest niedokładne: w praktyce niektóre problemy, o których nie wiadomo, że znajdują się w P, mają praktyczne rozwiązania, a niektóre, które są w P, nie, ale jest to przydatna zasada praktyczna .

Definicja

Język L w P, wtedy i tylko wtedy, gdy istnieje deterministycznej maszyny Turinga M , tak że

• M działa dla czasu wielomianowego na wszystkich wejściach
• Dla wszystkich wyjść x w L , M 1
• Dla wszystkich x nie w L , M wyjścia 0

P można również postrzegać jako jednolitą rodzinę obwodów binarnych . Język L jest w P wtedy i tylko wtedy, gdy istnieje jednorodna rodzina układów logicznych w czasie wielomianowym , taka, że ${\ Displaystyle \ {C_ {n}: n \ w \ mathbb {N} \}}$

• Dla wszystkich , wykonuje n bitów na wejściu i wyjść 1 bit${\ Displaystyle n \ w \ mathbb {N}}$${\ Displaystyle C_ {n}}$
• Dla wszystkich x w L ,${\ Displaystyle C_ {| x |} (x) = 1}$
• Dla wszystkich x nie w L ,${\ Displaystyle C_ {| x |} (x) = 0}$

Definicję obwodu można osłabić, aby używać tylko rodziny jednolitych przestrzeni logów bez zmiany klasy złożoności.

Znaczące problemy w P

Wiadomo, że P zawiera wiele naturalnych problemów, w tym wersje decyzyjne programowania liniowego i znajdowanie maksymalnego dopasowania . W 2002 roku pokazano, że problem określenia, czy liczba jest liczbą pierwszą, jest w P. Pokrewną klasą problemów funkcyjnych jest FP .

Kilka naturalnych problemów jest kompletnych dla P, w tym st -łączność (lub osiągalność ) na naprzemiennych grafach. Artykuł o problemach P-zupełnych wymienia dalsze istotne problemy w P.

Relacje z innymi klasami

Uogólnienie P to NP , które jest klasą problemów decyzyjnych rozstrzyganych przez niedeterministyczną maszynę Turinga działającą w czasie wielomianowym . Równoważnie jest to klasa problemów decyzyjnych, w której każda instancja „tak” ma certyfikat rozmiaru wielomianu, a certyfikaty mogą być sprawdzane przez wielomianową maszynę Turinga z deterministycznym czasem. Klasa problemów, dla których dotyczy to przypadków „nie”, nazywa się co-NP . P jest trywialnie podzbiorem NP i co-NP; większość ekspertów uważa, że ​​jest to odpowiedni podzbiór, chociaż ta ( hipoteza ) pozostaje nieudowodniona. Innym otwartym problemem jest to, czy NP = co-NP; ponieważ P = co-P, negatywna odpowiedź oznaczałaby . ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$

Wiadomo również, że P jest co najmniej tak duże jak L , klasa problemów rozstrzyganych w logarytmicznej ilości pamięci . Decydujący korzystający z przestrzeni nie może wykorzystać więcej niż czasu, ponieważ jest to całkowita liczba możliwych konfiguracji; zatem L jest podzbiorem P. Innym ważnym problemem jest to, czy L = P. Wiemy, że P = AL, zbiór problemów możliwych do rozwiązania w pamięci logarytmicznej przez naprzemienne maszyny Turinga . Wiadomo również, że P nie jest większe niż PSPACE , klasa problemów rozstrzyganych w przestrzeni wielomianowej. Ponownie, czy P = PSPACE jest otwartym problemem. Podsumowując: ${\ Displaystyle O (\ log n)}$${\ Displaystyle 2 ^ {O (\ log n)} = n ^ {O (1)}}$

${\displaystyle {\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}\subseteq {\mathsf {EXPTIME}}.}$

Tutaj EXPTIME jest klasą problemów rozwiązywalnych w czasie wykładniczym. Ze wszystkich klas pokazanych powyżej znane są tylko dwa ścisłe ograniczenia:

• P jest ściśle zawarte w EXPTIME. W związku z tym wszystkie problemy trudne do EXPTIME leżą poza P, a przynajmniej jedno z ograniczeń na prawo od P powyżej jest ścisłe (w rzeczywistości powszechnie uważa się, że wszystkie trzy są ścisłe).
• L jest ściśle zawarte w PSPACE.

Najtrudniejszymi problemami w P są problemy P-zupełne .

Innym uogólnieniem P jest P/poly lub niejednorodny czas wielomianowy. Jeśli problem występuje w P/poly, to można go rozwiązać w deterministycznym czasie wielomianowym, pod warunkiem, że podany zostanie łańcuch porad, który zależy tylko od długości wejścia. Jednak w przeciwieństwie do NP, maszyna czasu wielomianowego nie musi wykrywać fałszywych ciągów porad; nie jest weryfikatorem. P/poly to duża klasa zawierająca prawie wszystkie praktyczne problemy, w tym wszystkie BPP . Jeśli zawiera NP, hierarchia wielomianów zapada się na drugi poziom. Z drugiej strony zawiera również pewne niepraktyczne problemy, w tym pewne nierozstrzygalne problemy, takie jak jednoargumentowa wersja każdego nierozstrzygalnego problemu.

W 1999 Jin-Yi Cai i D. Sivakumar, opierając się na pracy Mitsunori Ogihary , pokazali, że jeśli istnieje rzadki język, który jest P-zupełny, to L = P.

Nieruchomości

Algorytmy wielomianowe są zamknięte w kompozycji. Intuicyjnie mówi to, że jeśli napisze się funkcję, która jest wielomianowa, zakładając, że wywołania funkcji są w czasie stałym, a jeśli te nazywane funkcje same wymagają czasu wielomianowego, to cały algorytm zajmuje czas wielomianowy. Jedną z konsekwencji tego jest to, że P samo w sobie jest niskie . Jest to również jeden z głównych powodów, dla których P jest uważane za klasę niezależną od maszyny; każda „cecha” maszyny, taka jak dostęp losowy , która może być symulowana w czasie wielomianowym, może być po prostu skomponowana z głównym algorytmem wielomianowym, aby zredukować ją do algorytmu wielomianowego na bardziej podstawowej maszynie.

Języki w P są również zamknięte w ramach odwrócenia, przecięcia , zjednoczenia , konkatenacji , domknięcia Kleene , homomorfizmu odwrotnego i komplementacji .

Czyste dowody istnienia algorytmów wielomianowych

Wiadomo, że niektóre problemy można rozwiązać w czasie wielomianowym, ale nie jest znany żaden konkretny algorytm do ich rozwiązania. Na przykład twierdzenie Robertsona-Seymoura gwarantuje, że istnieje skończona lista zabronionych nieletnich, która charakteryzuje (na przykład) zbiór grafów, które można osadzić na torusie; ponadto Robertson i Seymour wykazali, że istnieje algorytm O( n ³ ) określający, czy dany graf ma graf jako minor. Daje to niekonstruktywny dowód na to, że istnieje wielomianowy algorytm określający, czy dany graf może być osadzony na torusie, mimo że nie jest znany żaden konkretny algorytm dla tego problemu.

Charakterystyki alternatywne

W złożoności opisowej , P można opisać jako problemy wyrażalne w FO(LFP) , logice pierwszego rzędu z dodanym operatorem najmniej ustalonego punktu , na uporządkowanych strukturach. W podręczniku Immermana z 1999 roku poświęconym złożoności opisowej , Immerman przypisuje ten wynik Vardiemu i Immermanowi.

W 2001 roku opublikowano, że PTIME odpowiada (dodatnim) gramatyce konkatenacji zakresu .

Historia

Kozen twierdzi, że Cobhamowi i Edmondsowi „ogólnie przypisuje się wynalezienie pojęcia czasu wielomianowego”. Cobham wynalazł klasę jako niezawodny sposób charakteryzowania wydajnych algorytmów, prowadząc do tezy Cobhama . Jednak HC Pocklington w artykule z 1910 r. przeanalizował dwa algorytmy rozwiązywania kongruencji kwadratowych i zaobserwował, że jeden zajmuje czas „proporcjonalny do potęgi logarytmu modułu” i skontrastował go z algorytmem, który zajmuje czas proporcjonalny „do samego modułu”. lub jego pierwiastka kwadratowego”, w ten sposób wyraźnie rozróżniając algorytm działający w czasie wielomianowym od algorytmu, który nie działał.

Uwagi

Bibliografia

• Cobham, Alan (1965). „Wewnętrzna trudność obliczeniowa funkcji”. Proc. Logika, Metodologia i Filozofia Nauki II . Północna Holandia.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN  0-262-03293-7 . Sekcja 34.1: Czas wielomianowy, s. 971-979.
• Papadimitriou, Christos H. (1994). Złożoność obliczeniowa . Czytanie, Mass.: Addison-Wesley. Numer ISBN 978-0-201-53082-7.
• Sipser, Michael (2006). Wprowadzenie do teorii obliczeń, wydanie 2 . Kurs Technology Inc. ISBN 978-0-534-95097-2. Sekcja 7.2: Klasa P, s. 256–263;.

Linki zewnętrzne

• Złożoność Zoo : klasa P
• Złożoność Zoo : Klasa P/poli