P (złożoność)

Klasa P , czasami określana jako PTIME lub DTIME (n O (1) ), to bardzo ważna klasa teorii złożoności , dziedzina informatyki teoretycznej i matematyki . Z definicji, problem decyzyjny jest w P, jeśli jest rozstrzygany przez deterministyczną maszynę Turinga w czasie wielomianowym w odniesieniu do wielkości danych wejściowych. Mówimy, że problem rozstrzyga się w czasie wielomianowym .

Problemy w P są uważane za „wykonalne” ( wykonalne w języku angielskim), łatwe do rozwiązania (w tym sensie, że można to zrobić stosunkowo szybko). To teza Cobhama wydana przez amerykańskiego naukowca Alana Cobhama. René Lalement przypisuje tę tezę Cookowi. Klasa P jest zaliczana do klasy NP , co prowadzi do jednego z wielkich otwartych problemów teorii złożoności, a mianowicie: Czy P jest równe NP?

Przykłady problemów w P

Problem jest w P, jeśli istnieje algorytm, który decyduje o tym w czasie wielomianowym. Zacytujmy:

2SAT ograniczenia i HORNSAT SAT Problem jest w P .
Łączność na wykresie: Przykładem problemu wielomianowego jest łączność na wykresie. Biorąc pod uwagę graf z n wierzchołkami (uważamy, że rozmiar danych, a zatem wykresu, to liczba jego wierzchołków), chodzi o to, aby wiedzieć, czy wszystkie pary wierzchołków są połączone ścieżką. Algorytm przejścia dogłębne buduje drzewa rozpinającego wykresu zaczynając od wierzchołka. Jeśli to drzewo zawiera wszystkie wierzchołki wykresu, to wykres jest połączony. Czas potrzebny do zbudowania tego drzewa to co najwyżej ok . n ² (gdzie C jest stałą i n liczba wierzchołków grafu), więc problem jest w klasie P .

Ponadto, czasami dowód przynależności do P , który zwykle odbywa się poprzez odkrycie algorytmu wielomianowego, wymagał wielu lat badań:

Test AKS pierwszości jest algorytmem, w którym pokazano, że problem, czy jest liczbą całkowitą lub nie mogą zostać rozwiązane przez algorytm wielomianu.

Programowanie liniowe: Wszystkie algorytmy wewnętrzny punkt stosuje sklasyfikować programowania liniowego w klasie P . Ten problem jest nawet P -kompletny .

Definicje formalne

Klasyczna definicja przy użyciu maszyn Turinga

Oznaczamy przez CZAS ( t ( n )) klasę problemów decyzyjnych, które można rozstrzygnąć w czasie rzędu wielkości t ( n ) na maszynie deterministycznej (gdzie n jest rozmiarem wejścia). A więc z definicji

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

Definicja z obwodami

P można również zdefiniować za pomocą jednolitych rodzin obwodów boolowskich . Język L jest w P wtedy i tylko wtedy, gdy istnieje rodzina obwodów Boole'a , jednorodnych w czasie wielomianowym (tj. Istnieje deterministyczna maszyna Turinga, która wytwarza na wejściu 1 n ), na przykład ${\ Displaystyle \ {C_ {n}: n \ in \ mathbb {N} \}}$ $C_ {n}$

wszystkiego , ma n bity wejściowe i wyjściowe bitów zwrócić $n \ in \ mathbb {N}$ $C_ {n}$
Dla wszystkich x w L , ${\ Displaystyle C_ {| x |} (x) = 1}$
Dla wszystkich x, których nie ma w L , ${\ Displaystyle C_ {| x |} (x) = 0}$

Definicję za pomocą obwodów można osłabić stosując jednorodną rodzinę w przestrzeni logarytmicznej i zawsze podaje równoważną definicję dla klasy P. Jeśli rozluźnimy założenie jednorodności, określamy klasę P / poli .

Relacje z innymi klasami

Mamy oczywiste włączenie P NP , ale jednym z dużych otwartych pytań w informatyce teoretycznej jest problem P = NP? . $\ scriptstyle \ subseteq$

Możemy umieścić P w hierarchii języków, sklasyfikowanych według wymaganego miejsca: zawiera NL (klasa problemów, które można rozwiązać na niedeterministycznej maszynie w przestrzeni logarytmicznej) i jest zawarty w PSPACE (klasa problemów, która można rozwiązać na niedeterministycznej maszynie w przestrzeni logarytmicznej. rozwiązywać w przestrzeni wielomianowej). Wtrącenia są następujące (nie wiemy, czy są ścisłe):

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE P ≠ EXPTIME (zgodnie z deterministycznym twierdzeniem o hierarchii czasu )

Ponadto P jest pierwszym poziomem hierarchii wielomianów . A P jest zawarte w klasach wielomianów na mocniejszych maszynach (na przykład kwantowych lub przypadkowych), takich jak ZPP , BPP i BQP .

P-kompletne problemy

Problem decyzja mówi się, że P - kompletny lub kompletne do klasy P , jeżeli jest ona klasy P , a jeżeli błąd klasy P może być zmniejszony do A w logarytmicznej przestrzeni (to znaczy, że translacja od przykład X Spośród problem z instancją A można rozwiązać za pomocą spacji O (log | x |)). Następujące problemy są P- zakończone .

Horn-SAT: the Problem SAT ogólnie jest NP-zupełny , ale jego ograniczenie wyznacza Klauzula Horna jest w P . To jest P-kompletne.
Problem oceny obwodu : w języku angielskim problem z wartością obwodu (CVP) polega na określeniu, czy dla danego obwodu boolowskiego wynik funkcji wykonanej na danym wejściu odpowiada zadanej wartości.
Problem poznania, czy język oznaczony gramatyką algebraiczną jest pusty, czy nie.
Zdecyduj, czy język gramatyki algebraicznej jest nieskończony.
Problem sprawdzania modelu ( sprawdzanie modelu w języku angielskim) w formie logiki temporalnej CTL jest w P i został potwierdzony w P-zupełny. Dokładniej, dowód pokazuje, że modelowe sprawdzenie wzoru fragmentu syntaktycznego CTL z operatorami AX (dla dowolnego następcy) i EX (istnieje następca) jest P-trudne. Zatem sprawdzanie modelu wzoru logiki modalnej K jest P-zupełne.
Problem maksymalnego przepływu i dlatego prawdziwe programowanie liniowe .

Jeśli istnieje pusty język, który jest P-zupełny, to P = LOGSPACE .

Dodatkowe właściwości

W niektórych przypadkach mówimy o algorytmach czasu wielomianowego silnie lub słabo . To rozróżnienie istnieje dla problemów, których wpis zawiera liczby całkowite. Mówimy o słabo wielomianowym czasie, jeśli liczby całkowite muszą być podane w piśmie jednoargumentowym (tj. Liczba n liczy się jako rozmiar n ), aby mieć czas wielomianowy, i mówimy o silnie wielomianowym czasie, jeśli nawet zapis zwarty ( n ma rozmiar log ( n )) daje wielomian złożoności.

Zobacz też

Klasa NP

P / poly

Bibliografia

(en) Sanjeev Arora i Boaz Barak , Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , rozdz. 1 („Model obliczeniowy - i dlaczego to nie ma znaczenia”)

Link zewnętrzny

(en) Klasa P w Complexity Zoo

Uwagi i odniesienia

(w) Sanjeev Arora i Boaz Barak , Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , rozdz. 1 w notatkach historycznych.
Alan Cobham, „ The intrinsic computational trudne of functions ”, Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science , North Holland,1965.
René Lalement, rozdzielczość redukcji logiki , Masson, str. 344
Richard E. Ladner , „ Problem z wartością obwodu jest kompletny w logarytmicznej przestrzeni dla P ”, ACM SIGACT News , vol. 7, N O 1,1 st styczeń 1975, s. 18–20 ( ISSN 0163-5700 , DOI 10.1145 / 990518.990519 , czytaj online , dostęp 30 października 2018 )
„ Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak ” , na teoria.cs.princeton.edu (dostęp 30 października 2018 ) , s. 119, czw. 6,30
Neil D. Jones i William T. Laaser , „ Complete Problems for Deterministic Polynomial Time ”, Teor. Comput. Sci. , vol. 3, N O 1,1976, s. 105-117 ° C.
„ math.stackexchange.com ”
André Arnold i Paul Crubille , „ A Linear Algorithm to Solve Fixed Point Equations on Transition Systems ”, Inf. Proces. Łotysz. , vol. 29 N O 2Wrzesień 1988, s. 57–66 ( ISSN 0020-0190 , DOI 10.1016 / 0020-0190 (88) 90029-4 , odczyt w Internecie , dostęp 27 lutego 2019 r. )
EM Clarke , EA Emerson i AP Sistla , „ Automatic Verification of Finite-state Concurrent Systems Using Temporal Logic Specifications ”, ACM Trans. Program. Lang. Syst. , vol. 8, N O 2Kwiecień 1986, s. 244–263 ( ISSN 0164-0925 , DOI 10.1145 / 5397.5399 , czytaj online , dostęp 27 lutego 2019 )
Philippe Schnoebelen , The Complexity of Temporal Logic Model Checking ,1 st styczeń 2002( czytaj online ).
() „ Problem z maksymalnym przepływem to logarytmiczna przestrzeń dla pełnego P ” , Theoretical Computer Science , vol. 21, n o 1,1 st październik 1982, s. 105–111 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (82) 90092-5 , odczyt w Internecie , dostęp 8 listopada 2018 r. )
Jin-Yi Cai i D. Sivakumar , „ Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis ”, Journal of Computer and System Sciences , vol. 58 N O 21 st kwiecień 1999, s. 280–296 ( ISSN 0022-0000 , DOI 10.1006 / jcss.1998.1615 , czytaj online , dostęp 14 lipca 2019 )