P osztály

Az algoritmusok elméletében a P osztály (az angol  polinomból ) olyan feladatok halmaza, amelyekre léteznek „gyors” megoldási algoritmusok (amelyek futási ideje polinomiálisan függ a bemeneti adatok méretétől). A P osztály az algoritmusok szélesebb összetettségi osztályaiba tartozik .

Definíciók

Formális definíció

Az algoritmust egy determinisztikus Turing-gép azonosítja, amely a bemeneti szalagra adott bemeneti ábécé alapján számítja ki a kapott választ . Az algoritmus futási ideje egy rögzített x bemeneti szóra a Turing-gép munkaciklusainak száma a gép elejétől a megállításáig. Egy Turing-gép által kiszámított függvény összetettsége a bemeneti szó hosszától függ, és egyenlő a gép maximális futási idejével az összes rögzített hosszúságú bemeneti szón:

Ha egy f függvényre létezik olyan M Turing-gép , amely valamilyen c számra és elég nagy n , akkor azt mondjuk, hogy a P osztályba tartozik, vagy időben polinomiális.

A Church-Turing tézis szerint bármilyen elképzelhető algoritmus megvalósítható Turing-gépen. Bármely programozási nyelvhez hasonló módon definiálhat egy P osztályt (a definícióban a Turing-gépet a programozási nyelv implementációjával helyettesítve). Ha annak a nyelvnek a fordítója , amelyen az algoritmus megvalósul, polinomiálisan lelassítja az algoritmus végrehajtását (azaz az algoritmus végrehajtási ideje egy Turing-gépen kisebb, mint a végrehajtási idejének valamilyen polinomja egy programnyelvben), akkor a P osztályok definíciói erre a nyelvre és a Turing-gépre megegyeznek. Az összeállítás nyelvi kódja egy kis polinomiális lassítással átalakítható Turing-géppé, és mivel az összes létező nyelv lehetővé teszi az összeállításig történő fordítást (ismét polinomiális lassítással), a P osztály definíciói a Turing-gépekre és bármely meglévő programozási nyelvre ugyanazok.

Egy szűkebb meghatározás

Néha a P osztály a függvények szűkebb osztályát jelenti, nevezetesen a predikátumok osztályát (függvények ). Ebben az esetben az L nyelv , amelyet ez a predikátum ismer fel, azoknak a szavaknak a halmaza, amelyeken az állítmány egyenlő 1-gyel. A P osztály nyelvei azok a nyelvek, amelyekhez az osztály predikátumai vannak. Nyilvánvaló, hogy ha a és nyelvek a P osztályba tartoznak, akkor egyesülésük, metszéspontjuk és kiegészítésük is a P osztályba tartozik.

A P osztály felvétele más osztályokba

A P osztály az egyik legszűkebb összetettségi osztály. A hozzá tartozó algoritmusok szintén az NP osztályba tartoznak , a BPP osztályba (mivel lehetővé teszik a polinomiális megvalósítást nulla hibával), a PSPACE osztályba (mivel a Turing-gépen a munkaterület mindig kisebb, mint az idő), a P/Poly osztály (ennek bizonyítására a koncepció a gép protokollját használja, amelyet polinom méretű Boole -sémává alakítanak át).

Több mint 30 éve megoldatlan maradt a P és NP osztályok egyenlőségének problémája . Ha egyenlőek, akkor az NP osztály bármely problémája gyorsan (polinomiális időben) megoldható. A tudományos közösség azonban hajlik erre a kérdésre a negatív válasz felé. Ezen túlmenően a szélesebb osztályokba, például a PSPACE-be való felvétel szigorúsága nem bizonyított, de a P és a PSPACE egyenlősége jelenleg nagyon kétségesnek tűnik.

Problémapéldák

A P osztályhoz tartozó problémák

P osztályú problémák például egész számok összeadása, szorzása, osztása, osztás maradékának felvétele, mátrixszorzás , gráfok összefüggéseinek megállapítása, n szám halmazának rendezése, Euler -ciklus keresése m éles gráfon, néhány keresése szó egy n hosszúságú szövegben, minimális költségfák felépítése, lineáris programozás és néhány más.

Problémák, amelyeknek a P osztályban való tagsága ismeretlen

Sok olyan probléma van, amelyre nem találtak polinomiális algoritmust, de nem bizonyították, hogy nem létezik. Ennek megfelelően nem ismert, hogy az ilyen problémák a P osztályba tartoznak-e. Íme néhány közülük:

1. Az utazó eladó probléma (valamint az összes többi NP-teljes probléma ). A feladat polinomiális megoldása egyenértékű a P és NP osztályok egyenlőségének megállapításával .
2. Egy szám felbontása prímtényezőkre .
3. Diszkrét logaritmus véges mezőben .
4. Rejtett alcsoport-probléma n generátorral .
5. Diszkrét logaritmus egy elliptikus görbe pontjainak additív csoportjában .

Gyakorlati érték

Mivel gyakran nagy bemeneti adatokon kell kiszámítani a függvények értékét, nagyon fontos feladat a polinomiális algoritmusok megtalálása a függvények kiszámításához. Úgy gondolják, hogy sokkal nehezebb kiszámítani azokat a függvényeket, amelyek nem tartoznak a P osztályba, mint azokat, amelyek tartoznak. A P osztályba tartozó algoritmusok többségének bonyolultsága nem haladja meg a bemeneti adatok méretének kis fokú polinomját. Például a szabványos mátrixszorzási algoritmus n3 szorzást igényel ( bár léteznek gyorsabb algoritmusok, mint például a Strassen -algoritmus ). A polinom mértéke ritkán nagy. Az egyik ilyen eset az indiai matematikusok által 2002 -ben javasolt Agrawal-Kayala-Saksena teszt , amely kideríti, hogy az n szám prím -e az O (log 6 n ) műveletekben.

Irodalom

• Thomas H. Kormen és munkatársai Algoritmusok: Konstrukció és elemzés = Introduction to Algorithms. - 2. kiadás - M . : "Williams" , 2006. - 1296 p. — ISBN 0-07-013151-1 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M . : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .

Linkek