Klasse P

I teorien om algoritmer er klassen P ( fra det engelske  polynomium ) et sæt af problemer, for hvilke der findes "hurtige" løsningsalgoritmer (hvis køretiden afhænger polynomisk af størrelsen af ​​inputdataene). P-klassen er inkluderet i bredere kompleksitetsklasser af algoritmer.

Definitioner

Formel definition

Algoritmen identificeres med en deterministisk Turing-maskine , der beregner svaret givet et ord fra input-alfabetet givet til input-båndet . Køretiden for algoritmen for et fast inputord x er antallet af arbejdscyklusser for Turing-maskinen fra maskinens start til stop. Kompleksiteten af ​​en funktion beregnet af en Turing-maskine er en funktion , der afhænger af længden af ​​inputordet og er lig med maskinens maksimale køretid over alle inputord af en fast længde:

Hvis der for en funktion f eksisterer en Turing-maskine M , så den for et eller andet tal c og tilstrækkelig stor n , så siges den at tilhøre klassen P eller er polynomium i tid.

Ifølge Church-Turing-afhandlingen kan enhver tænkelig algoritme implementeres på en Turing-maskine. For ethvert programmeringssprog kan du definere en klasse P på lignende måde (erstatning af Turing-maskinen i definitionen med en implementering af programmeringssproget). Hvis kompilatoren af ​​sproget, som algoritmen er implementeret i, sænker udførelsen af ​​algoritmen polynomielt (det vil sige, at eksekveringstiden for algoritmen på en Turing-maskine er mindre end et eller andet polynomium af dens udførelsestid i et programmeringssprog), så definitionerne af klasserne P for dette sprog og for Turing-maskinen er de samme. Assembly sprogkode kan konverteres til en Turing-maskine med en lille polynomiel opbremsning, og da alle eksisterende sprog tillader kompilering til assemblering (igen med polynomial slowdown), definitionerne af P-klassen for Turing-maskiner og for ethvert eksisterende programmeringssprog er det samme.

En snævrere definition

Nogle gange betyder klassen P en snævrere klasse af funktioner, nemlig klassen af ​​prædikater (funktioner ). I dette tilfælde er sproget L , som genkendes af dette prædikat, det sæt af ord, hvor prædikatet er lig med 1. Sprogene i klassen P er de sprog, for hvilke der er prædikater i klassen P, der genkender dem. Det er indlysende, at hvis sprogene og ligger i klassen P, så hører deres forening, skæringspunkt og komplementer også til klassen P.

Inklusioner af klassen P i andre klasser

Klasse P er en af ​​de smalleste kompleksitetsklasser. Algoritmerne, der tilhører ham, tilhører også NP -klassen , BPP-klassen (da de tillader en polynomielimplementering med nul fejl), PSPACE-klassen (fordi arbejdsområdet på en Turing-maskine altid er mindre end tiden), P/Poly-klassen (for at bevise dette faktum, er konceptet brugt protokol for maskinen, som konverteres til et boolsk skema af polynomisk størrelse).

I mere end 30 år har problemet med ligestilling mellem klasserne P og NP været uløst . Hvis de er ens, så kan ethvert problem fra NP-klassen løses hurtigt (i polynomisk tid). Imidlertid hælder det videnskabelige samfund til det negative svar på dette spørgsmål. Derudover er strengheden af ​​inklusion i bredere klasser, for eksempel i PSPACE, ikke blevet bevist, men ligestillingen mellem P og PSPACE ser meget tvivlsom ud i øjeblikket.

Eksempler på problemer

Problemer tilhørende klasse P

Eksempler på problemer fra klasse P er heltalsaddition, multiplikation, division, at tage resten af ​​divisionen, matrixmultiplikation , finde ud af sammenhængen mellem grafer , sortere et sæt af n tal, finde en Euler-cyklus på en graf med m kanter, finde nogle ord i en tekst af længden n, der konstruerer en dækkende minimumsomkostningstræer, lineær programmering og nogle andre.

Problemer, hvis medlemskab i klassen P er ukendt

Der er mange problemer, som der ikke er fundet en polynomiel algoritme for, men det er ikke bevist, at den ikke eksisterer. Det vides derfor ikke, om sådanne problemer tilhører klasse P. Her er nogle af dem:

1. Problemet med den rejsende sælger (såvel som alle andre NP-komplet problemer ). Den polynomielle løsning af dette problem svarer til at etablere ligheden mellem klasserne P og NP .
2. Dekomponering af et tal i primfaktorer .
3. Diskret logaritme i et begrænset felt .
4. Skjult undergruppeproblem med n generatorer.
5. Diskret logaritme i en additiv gruppe af punkter på en elliptisk kurve .

Praktisk værdi

Da det ofte er nødvendigt at beregne værdierne af funktioner på store inputdata, er det en meget vigtig opgave at finde polynomielle algoritmer til beregning af funktioner. Det menes, at det er meget sværere at beregne funktioner, der ikke tilhører klassen P, end dem, der gør. De fleste af algoritmerne i klasse P har en kompleksitet, der ikke overstiger et polynomium af lille grad på størrelsen af ​​inputdataene. For eksempel kræver standardmatrixmultiplikationsalgoritmen n 3 multiplikationer (selvom der findes hurtigere algoritmer, såsom Strassens algoritme ). Graden af ​​et polynomium er sjældent stor. Et sådant tilfælde er Agrawal-Kayala-Saksena-testen foreslået i 2002 af indiske matematikere , som finder ud af, om tallet n er primtal i O (log 6 n ) operationer.

Litteratur

• Thomas H. Kormen et al. Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M . : "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Links