Sharp-P-complet
# P-complet (pronunțat "P ascuțit complet" sau uneori "număr P complet" sau "hash P complet") este o clasă de complexitate în teoria complexității de calcul . Prin definiție, o problemă este # P-completă dacă și numai dacă este în #P , și orice problemă din #P poate fi redusă la aceasta printr-o reducere a numărului de timp polinomial , adică printr-o reducere de Turing a timpului polinomial relativ la cardinalitate de seturi de soluții . În mod echivalent, o problemă este # P-completă dacă și numai dacă este în #P , iar pentru orice mașină Turing nedeterministă („mașină NP”), problema calculării numărului de căi de acceptare poate fi redusă la această problemă.
Exemple de probleme # P-complete includ:
- Câte alocări variabile diferite vor satisface o formulă generală booleană dată? ( #SAT )
- Câte alocări de variabile diferite vor satisface o anumită formulă FND ?
- Câte alocări de variabile diferite vor satisface o anumită formulă 2SAT ?
- Câte potriviri perfecte există pentru un grafic bipartit dat?
- Care este valoarea permanentă a unei matrice date al cărei venit este 0 sau 1? (Vezi Permanent este ascuțit-P-plin .)
- Câte colorări ale graficelor folosind k culori există pentru un anumit grafic G ?
- Câte extensii liniare diferite există pentru un ordin parțial dat sau, în mod echivalent, câte ordonări topologice diferite există pentru un grafic aciclic direct dat? [1]
Un algoritm de timp polinomial pentru rezolvarea unei probleme # P-complete, dacă ar exista, ar implica P = NP , deci P = PH . În prezent nu se cunoaște un astfel de algoritm.
Probleme ușoare cu versiunile dificile de numărare
Este surprinzător faptul că unele probleme # P-complete corespund unor probleme P complete. Este foarte ușor să determinați satisfacția unei formule booleene în FND: o astfel de formulă este satisfăcătoare dacă și numai dacă conține o conjuncție satisfăcătoare (una care nu conține o variabilă și negarea acesteia), în timp ce numărarea numărului de sarcini satisfăcătoare este # P-complet. Decizia 2-SAT este, de asemenea, ușoară, spre deosebire de numărul de sarcini satisfăcătoare. Sortarea topologică este ușoară spre deosebire de numărarea numărului de sortări topologice. Aceeași observație se poate face și pentru problema cuplării perfecte. Se știa înainte că problema deciziei "Există o potrivire perfectă pentru un anumit grafic bipartit?" poate fi rezolvat în timp polinomial și, de fapt, pentru un grafic cu vârfuri V și muchii E , poate fi rezolvat în timp O ( VE ). Întrebarea corespunzătoare „Câte potriviri perfecte are graficul bipartit dat?” este deja # P-complet. Problema numărării numărului de perechi perfecte (sau în grafice directe: știm că numărul de acoperiri ale ciclului de vârf este echivalent cu problema calculului permanentului unei matrice . Problema numărării perechilor perfecte a fost prima problemă a numărului corespunzând unei probleme ușoare P care s-a dovedit a fi # P-completă, într-un eseu din 1979 realizat de Leslie Valiant, care a definit și pentru prima dată clasele #P și # P-complete. [2]
Apropiere
Există algoritmi probabilistici care returnează aproximări bune la unele probleme # P-complete cu probabilitate mare. Aceasta este una dintre demonstrațiile puterii algoritmilor probabilistici.
Multe probleme # P-complete au o schemă de aproximare randomizată complet polinomială sau „FPRAS”, care, în mod informal, va produce foarte probabil o aproximare la un grad arbitrar de precizie, într-un timp care este atât polinom, cât și dimensiunea problemei asta până la gradul de precizie necesar. Jerrum , Valiant și Vazirani au arătat că fiecare problemă # P-completă are fie FPRAS, fie este în esență imposibil de aproximat; dacă există vreun algoritm de timp polinomial care produce în mod consecvent o aproximare a unei probleme # P-complete care se află într-un raport care are dimensiunea de intrare a răspunsului corect, atunci acel algoritm poate fi folosit pentru a construi un FPRAS. [3]
Notă
- ^ Graham R. Brightwell și Peter Winkler , Counting linear extensions , în ordine , vol. 8, nr. 3, 1991, 225–242, DOI : 10.1007 / BF00383444 .
- ^ Leslie G. Valiant, Complexitatea calculului permanentului , în Informatică teoretică , vol. 8, nr. 2, Elsevier, 1979, 189–201, DOI : 10.1016 / 0304-3975 (79) 90044-6 .
- ^ Mark R. Jerrum, Leslie G. Valiant; Vijay V. Vazirani, Generarea aleatorie de structuri combinatorii dintr-o distribuție uniformă , în Theoretical Computer Science , vol. 32, Elsevier, 1986, 169–188.
Lecturi suplimentare
- Vijay V. Vazirani, Algoritmi de aproximare , Berlin, Springer, 2003, ISBN 3-540-65367-8 .
linkuri externe
- (EN) Clasa # P-completă Depusă la 19 ianuarie 2018 în Internet Archive . pe complexitatea zoologică
