A P és NP osztályok egyenlősége

A P és NP komplexitási osztályok egyenlőségének kérdése (az orosz forrásokban számbavételi problémaként is ismert [1] [2] ) több mint három évtizede az egyik központi nyitott probléma az algoritmusok elméletében . Ha igenlő választ adunk rá, ez azt jelenti, hogy elméletileg sokkal gyorsabban lehet megoldani sok összetett problémát, mint most.

A P és NP osztályok közötti kapcsolattal az algoritmuselmélet egyik ága, a számítási komplexitás elmélete foglalkozik . Egy probléma megoldásához szükséges erőforrásokat tanulmányozza. A leggyakoribb erőforrások az idő (hány lépést kell megtenni) és a memória (mennyi memória szükséges egy feladat elvégzéséhez).

A P és NP osztályok egyenlőségének problémája egyike annak a hét millenniumi feladatnak, amelyekért az Agyag Matematikai Intézet egymillió dolláros díjat ítélt oda .

Megfogalmazás

Lazán a P = NP egyenlőségi probléma a következő: ha egy kérdésre adott pozitív válasz meglehetősen gyorsan ( polinomiális időben ) ellenőrizhető , akkor igaz-e, hogy erre a kérdésre elég gyorsan meg lehet találni a választ (polinomban is idő és polinomiális memória használata )? Más szóval, valóban nem könnyebb ellenőrizni a probléma megoldását, mint megtalálni? [3]

Például igaz-e, hogy a { ​​−2 , −3 , 15 , 14 , 7 , −10 , …} számok között vannak olyanok, amelyek összege 0 ( részhalmazösszeg feladat )? A válasz igen , mert a −2 −3 + 15 −10 = 0 néhány kiegészítéssel könnyen ellenőrizhető (a pozitív válasz ellenőrzéséhez szükséges információt tanúsítványnak nevezzük ). Ebből következik, hogy ezeket a számokat ugyanolyan könnyű felvenni? A tanúsítvány ellenőrzése olyan egyszerű, mint megtalálni? Úgy tűnik, a számok felvétele nehezebb, de ez nem bizonyított.

A P és NP osztályok definíciójából közvetlenül következik a következmény: . Ennek a felvételnek a szigorúságáról azonban egyelőre semmit sem tudni, vagyis arról, hogy van-e olyan probléma, ami az NP -ben rejlik, de a P -ben nem . Ha ilyen probléma nem létezik, akkor az NP osztályba tartozó összes probléma megoldható polinomiális időben, ami óriási előnyt ígér a számítási sebességben. Most az NP osztály legbonyolultabb problémái (az úgynevezett NP - teljes problémák ) exponenciális idő alatt megoldhatók, ami gyakorlati szempontból elfogadhatatlan.

Történelem

A számítási bonyolultság kérdését valószínűleg Kurt Gödel tette fel először 1956-ban Neumann Jánosnak írt levelében , amelyben azt kérdezte, hogy egy (ma ismert, hogy NP-teljes) probléma megoldható-e másodfokú vagy lineáris időben. Ugyanakkor Gödel azt javasolta, hogy ha létezik megoldás, akkor ez lehetővé teszi a számítógépek számára számos matematikai probléma megoldását [4] .

Az osztályegyenlőség kérdését először Stephen Cook vetette fel 1971- ben [5] és egymástól függetlenül Leonid Levin 1973 - ban [6] .

A 2000-es évek elején a legtöbb matematikus úgy véli, hogy ezek az osztályok nem egyenlőek. Egy 2002 -ben 100 tudós körében végzett felmérés szerint [7] 61 ember gondolja úgy, hogy a válasz "nem egyenlő", 9 - "egyenlő", 22-en nehéznek találták a választ, 8-an pedig úgy vélik, hogy a hipotézis nem vezethető le a jelenlegiből. axiómarendszer , és így nem lehet sem bizonyítani, sem cáfolni.

Más jól ismert megoldatlan matematikai problémákhoz hasonlóan ennek a problémának a megoldására tett kísérletek is jelentős erőfeszítéseket igényelnek; A P és NP osztályok egyenlőségének vagy egyenlőtlenségének téves bizonyítékait rendszeresen publikálják (nem a tudományos irodalomban), általában nem szakemberek [8] .

A P és NP osztályok egyenlőtlenségét feltételező védelmi rendszerek

Bármely nyilvános kulcsú titkosítási rendszer egyirányú függvények létezésének feltételezésén és/vagy egy bizonyos probléma megoldásának extrém időtartamán alapul (például az RSA algoritmusnál ez nagyon nagy számok faktorizálása).

A számítógépes rendszerek szolgáltatással való visszaélésekkel szembeni védelme érdekében a kérelmező felet egy olyan probléma megoldására kérik, amelynek megoldása sok időt vesz igénybe, és az eredményt a kiszolgáló könnyen és gyorsan ellenőrzi. Az ilyen spam elleni védelemre példa a Hashcash [9] rendszer , amely részleges inverziós hash -t használ az e-mailek küldésekor.

A proof-of-work technológián alapuló blokkláncok megkövetelik, hogy az eredményül kapott hash összeg kisebb legyen, mint a célérték. A kívánt hash összeg keresésének folyamata megköveteli annak ismételt újraszámítását a kiegészítő paraméter tetszőleges értékeinek felsorolásával (további részletekért lásd: Bányászat ). A rendszerben lévő összes számítógép jelentős időt tölt egy kielégítő hash-összeg keresésével (például Bitcoinban ez átlagosan 10 percet jelent minden bányász esetében ). Egy már kialakított blokk helyességének ellenőrzéséhez csak egyetlen hash számítás szükséges.

Hasonló problémák

Lásd még

Jegyzetek

  1. ↑ A. A. Razborov. P ?= NP avagy a felsorolás problémája: kitekintés a 90-es évekből .
  2. ↑ A. H. Shen . A felsorolási probléma  // PostNauka .
  3. ↑ Stuart, 2015 , p. 291.
  4. ↑ Hartmanis, Juris. Gödel, von Neumann és a P = NP probléma  (neopr.)  // Bulletin of the European Association for Theoretical Computer Science. - T. 38 . - S. 101-107 .
  5. ↑ Stephen Cook. The Importance of the P versus NP Question Archivált : 2011. július 9. a Wayback Machine -nél .
  6. ↑ L. A. Levin. Univerzális felsorolási  problémák // Az információtovábbítás problémái. - 1973. - T. 9 , 3. sz . - S. 115-116 .
  7. ↑ William I. Gasarch. A P=?NP közvélemény -kutatás  (neopr.)  // SIGACT News. - 2002. - T. 33 , 2. sz . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
  8. ↑ Lenta.ru – Múlt. A matematikusok végleg elvesztették hitüket az ezredforduló problémájának megoldásában . Letöltve: 2010. augusztus 26. Az eredetiből archiválva : 2010. augusztus 30.
  9. ↑ Hashcash – A szolgáltatásmegtagadás elleni ellenintézkedés (2002)
  10. ↑ Razborov, 2016 , p. 24.
  11. ↑ MIP* = RE: Mérföldkőnek számító számítástechnikai bizonyíték, amely dominóhatást okozott a fizikában és a matematikában / RUVDS.com Blog / Sudo Null IT News . Letöltve: 2020. december 24. Az eredetiből archiválva : 2021. május 12.
  12. ↑ [https://web.archive.org/web/20210119084755/https://arxiv.org/abs/2001.04383 Archiválva : 2021. január 19. a Wayback Machine -nél [2001.04383] MIP*=RE]

Irodalom

Linkek

  Ugrás a Wikidata elemre  Szótárak és enciklopédiák