Klass P

I teorin om algoritmer är klassen P (från det engelska  polynomet ) en uppsättning problem för vilka det finns "snabba" lösningsalgoritmer (vars gångtid beror polynomiellt på storleken på indata). P-klassen ingår i bredare komplexitetsklasser av algoritmer.

Definitioner

Formell definition

Algoritmen identifieras med en deterministisk Turing-maskin som beräknar svaret givet ett ord från inmatningsalfabetet som ges till inmatningsbandet . Drifttiden för algoritmen för ett fast inmatningsord x är antalet arbetscykler för Turing-maskinen från maskinens start till stopp. Komplexiteten hos en funktion som beräknas av en Turing-maskin är en funktion som beror på längden på inmatningsordet och är lika med maskinens maximala körtid över alla inmatningsord med en fast längd:

Om det för en funktion f finns en Turingmaskin M så att för något tal c och tillräckligt stort n , så sägs den tillhöra klassen P, eller är polynom i tid.

Enligt Church-Turing-avhandlingen kan alla tänkbara algoritmer implementeras på en Turing-maskin. För vilket programmeringsspråk som helst kan du definiera en klass P på liknande sätt (ersätt Turing-maskinen i definitionen med en implementering av programmeringsspråket). Om kompilatorn av språket där algoritmen är implementerad saktar ner exekveringen av algoritmen polynomiellt (det vill säga exekveringstiden för algoritmen på en Turing-maskin är mindre än något polynom av dess exekveringstid i ett programmeringsspråk), då Definitionerna av klasserna P för detta språk och för Turing-maskinen är desamma. Assembly språkkod kan konverteras till en Turing-maskin med lite polynomavmattning, och eftersom alla befintliga språk tillåter kompilering för montering (återigen, med polynomavmattning), definitionerna av P-klassen för Turing-maskiner och för alla befintliga programmeringsspråk är samma.

En snävare definition

Ibland betyder klassen P en smalare klass av funktioner, nämligen klassen av predikat (funktioner ). I det här fallet är språket L , som känns igen av detta predikat, den uppsättning ord på vilka predikatet är lika med 1. Språken i klassen P är de språk för vilka det finns predikat i klassen P som känner igen dem. Det är uppenbart att om språken och ligger i klassen P, så tillhör deras förening, skärningspunkt och komplement också klassen P.

Inkludering av klassen P i andra klasser

Klass P är en av de smalaste komplexitetsklasserna. Algoritmerna som tillhör honom tillhör också NP -klassen , BPP-klassen (eftersom de tillåter en polynomimplementering med noll fel), PSPACE-klassen (eftersom arbetsområdet på en Turing-maskin alltid är mindre än tiden), P/Poly-klassen (för att bevisa detta faktum används konceptet protokoll för maskinen, som omvandlas till ett booleskt schema av polynomstorlek).

I mer än 30 år har problemet med jämlikheten mellan klasserna P och NP varit olöst . Om de är lika kan alla problem från NP-klassen lösas snabbt (i polynomtid). Men det vetenskapliga samfundet lutar mot det negativa svaret på denna fråga. Dessutom har striktheten av inkludering i bredare klasser, till exempel i PSPACE, inte bevisats, men likheten mellan P och PSPACE ser mycket tveksam ut för tillfället.

Problemexempel

Problem som hör till klass P

Exempel på problem från klass P är heltalsaddition, multiplikation, division, att ta resten av divisionen, matrismultiplikation , ta reda på sambanden mellan grafer , sortera en uppsättning n tal, hitta en Euler-cykel på en graf med m kanter, hitta några ord i en text med längden n, konstruerar en täckande minimikostnadsträd, linjär programmering och några andra.

Problem vars medlemskap i klassen P är okänt

Det finns många problem för vilka ingen polynomalgoritm har hittats, men det har inte bevisats att den inte existerar. Följaktligen är det inte känt om sådana problem tillhör klass P. Här är några av dem:

1. Problemet med resande säljare (liksom alla andra NP-kompletta problem ). Polynomlösningen av detta problem är likvärdig med att fastställa likheten för klasserna P och NP .
2. Nedbrytning av ett tal till primtalsfaktorer .
3. Diskret logaritm i ett ändligt fält .
4. Dolt undergruppsproblem med n generatorer.
5. Diskret logaritm i en additiv grupp av punkter på en elliptisk kurva .

Praktiskt värde

Eftersom det ofta är nödvändigt att beräkna värdena för funktioner på stora indata, är det en mycket viktig uppgift att hitta polynomalgoritmer för att beräkna funktioner. Man tror att det är mycket svårare att beräkna funktioner som inte tillhör klassen P än de som gör det. De flesta av algoritmerna i klass P har en komplexitet som inte överstiger ett polynom av liten grad på storleken på indata. Till exempel kräver standardmatrismultiplikationsalgoritmen n 3 multiplikationer (även om det finns snabbare algoritmer, såsom Strassens algoritm ). Graden av ett polynom är sällan stor. Ett sådant fall är Agrawal-Kayala-Saksena-testet som föreslagits 2002 av indiska matematiker , som tar reda på om talet n är primtal i O (log 6 n ) operationer.

Litteratur

• Thomas H. Kormen et al Algoritmer: Konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M . : "Williams" , 2006. - 1296 sid. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M . : "Williams" , 2002. - 528 sid. - ISBN 0-201-44124-1 .

Länkar