Clasa P

În teoria algoritmilor, clasa P (din polinomul englezesc  ) este un set de probleme pentru care există algoritmi de rezolvare „rapidă” (al căror timp de rulare depinde polinom de mărimea datelor de intrare). Clasa P este inclusă în clasele de complexitate mai largi ale algoritmilor.

Definiții

Definiție formală

Algoritmul este identificat cu o mașină Turing deterministă care calculează răspunsul dat unui cuvânt din alfabetul de intrare dat casetei de intrare . Timpul de rulare al algoritmului pentru un cuvânt fix de intrare x este numărul de cicluri de lucru ale mașinii Turing de la pornirea până la oprirea mașinii. Complexitatea unei funcții calculate de o mașină Turing este o funcție care depinde de lungimea cuvântului de intrare și este egală cu timpul maxim de funcționare al mașinii pentru toate cuvintele de intrare cu o lungime fixă:

Dacă pentru o funcție f există o mașină de Turing M astfel încât pentru un număr c și n suficient de mare , atunci se spune că aparține clasei P sau este polinom în timp.

Conform tezei Church-Turing , orice algoritm imaginabil poate fi implementat pe o mașină Turing. Pentru orice limbaj de programare, puteți defini o clasă P într-un mod similar (înlocuind mașina Turing în definiție cu o implementare a limbajului de programare). Dacă compilatorul limbajului în care este implementat algoritmul încetinește execuția algoritmului polinomial (adică timpul de execuție a algoritmului pe o mașină Turing este mai mic decât un polinom al timpului său de execuție într-un limbaj de programare), atunci definițiile claselor P pentru acest limbaj și pentru mașina Turing sunt aceleași. Codul limbajului de asamblare poate fi convertit într-o mașină Turing cu o mică încetinire polinomială și, deoarece toate limbajele existente permit compilarea la asamblare (din nou, cu încetinire polinomială), definițiile clasei P pentru mașinile Turing și pentru orice limbaj de programare existent sunt la fel.

O definiție mai restrânsă

Uneori, clasa P înseamnă o clasă mai restrânsă de funcții, și anume clasa de predicate (funcții ). În acest caz, limba L , care este recunoscută de acest predicat, este mulțimea de cuvinte pe care predicatul este egal cu 1. Limbile clasei P sunt limbile pentru care există predicate ale clasei P care le recunosc. Este evident că, dacă limbile și se află în clasa P, atunci uniunea, intersecția și complementele lor aparțin și ele clasei P.

Includerea clasei P în alte clase

Clasa P este una dintre cele mai restrânse clase de complexitate. Algoritmii care îi aparțin aparțin și clasei NP , clasei BPP (deoarece permit o implementare polinomială cu eroare zero), clasei PSPACE (deoarece aria de lucru pe o mașină Turing este întotdeauna mai mică decât timpul), clasa P/Poly (pentru a demonstra acest fapt, se folosește conceptul de protocol al mașinii, care este convertit într-o schemă booleană de dimensiune polinomială).

De mai bine de 30 de ani, problema egalității claselor P și NP a rămas nerezolvată . Dacă sunt egale, atunci orice problemă din clasa NP poate fi rezolvată rapid (în timp polinomial). Cu toate acestea, comunitatea științifică înclină spre răspunsul negativ la această întrebare. În plus, strictețea includerii în clase mai largi, de exemplu, în PSPACE, nu a fost dovedită, dar egalitatea dintre P și PSPACE pare foarte îndoielnică în acest moment.

Exemple de probleme

Probleme aparținând clasei P

Exemple de probleme din clasa P sunt adunarea întregului, înmulțirea, împărțirea, luarea restului de diviziune, înmulțirea matriceală , aflarea conexiunii graficelor , sortarea unei mulțimi de n numere, găsirea unui ciclu Euler pe un grafic de m muchii, găsirea unora cuvânt într-un text de lungime n, construirea unui arbore de cost minim care acoperă, programare liniară și altele.

Probleme a căror apartenență la clasa P este necunoscută

Există multe probleme pentru care nu s-a găsit un algoritm polinom, dar nu s-a dovedit că nu există. În consecință, nu se știe dacă astfel de probleme aparțin clasei P. Iată câteva dintre ele:

1. Problema vânzătorului ambulant (precum și toate celelalte probleme NP-complete ). Rezolvarea polinomială a acestei probleme este echivalentă cu stabilirea egalității claselor P și NP .
2. Descompunerea unui număr în factori primi .
3. Logaritm discret într-un câmp finit .
4. Problemă subgrup ascuns cu n generatoare.
5. Logaritm discret într-un grup aditiv de puncte pe o curbă eliptică .

Valoare practică

Deoarece este adesea necesar să se calculeze valorile funcțiilor pe date de intrare mari, găsirea de algoritmi polinomi pentru calcularea funcțiilor este o sarcină foarte importantă. Se crede că este mult mai dificil de calculat funcțiile care nu aparțin clasei P decât cele care aparțin. Majoritatea algoritmilor din clasa P au o complexitate care nu depășește un polinom de grad mic pe dimensiunea datelor de intrare. De exemplu, algoritmul standard de multiplicare a matricei necesită n 3 înmulțiri (deși există algoritmi mai rapizi, cum ar fi algoritmul lui Strassen ). Gradul unui polinom este rareori mare. Un astfel de caz este testul Agrawal-Kayala-Saksena propus în 2002 de matematicienii indieni , care descoperă dacă numărul n este prim în operații O (log 6 n ).

Literatură

• Thomas H. Kormen et al.Algorithms : Construction and Analysis = Introduction to Algorithms. - Ed. a II-a. - M . : „Williams” , 2006. - 1296 p. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .

Link -uri