Jämlikhet mellan klasserna P och NP

Frågan om jämlikheten mellan komplexitetsklasserna P och NP (i ryska källor även känd som uppräkningsproblemet [1] [2] ) har varit ett av de centrala öppna problemen inom teorin om algoritmer i mer än tre decennier. Om ett jakande svar ges på det kommer det att innebära att det är teoretiskt möjligt att lösa många komplexa problem mycket snabbare än nu.

Relationen mellan klasserna P och NP behandlas i en gren av algoritmteorin som kallas beräkningskomplexitetsteori . Den studerar de resurser som behövs för att lösa något problem. De vanligaste resurserna är tid (hur många steg som ska tas) och minne (hur mycket minne som krävs för att slutföra en uppgift).

Problemet med jämlikheten mellan klasserna P och NP är ett av de sju millennieproblem som Clay Mathematical Institute tilldelade ett pris på en miljon US-dollar för .

Formulering

Löst sett är likhetsproblemet P = NP följande: om ett positivt svar på någon fråga kan kontrolleras ganska snabbt (i polynomtid ), så är det sant att svaret på denna fråga kan hittas ganska snabbt (även i polynom tid och använda polynomminne )? Med andra ord, är det verkligen inte lättare att kontrollera lösningen på problemet än att hitta den? [3]

Till exempel, är det sant att det bland talen { −2 , −3 , 15 , 14 , 7 , −10 , …} finns sådana att deras summa är lika med 0 ( submängdsummaproblem )? Svaret är ja , eftersom −2 −3 + 15 −10 = 0 lätt verifieras med några tillägg (informationen som behövs för att verifiera ett positivt svar kallas ett certifikat ). Följer det att det är lika enkelt att plocka upp dessa siffror? Är det lika enkelt att kontrollera ett certifikat som att hitta det? Det verkar som att det är svårare att plocka upp siffror, men detta har inte bevisats.

Från definitionen av klasserna P och NP följer omedelbart följden: . Inget är dock känt hittills om hur strikt denna inkludering är, det vill säga om det finns ett problem som ligger i NP men inte ligger i P. Om ett sådant problem inte existerar kan alla problem som tillhör klassen NP lösas i polynomtid, vilket lovar en enorm fördel i beräkningshastighet. Nu kan de mest komplexa problemen från NP -klassen (de så kallade NP - kompletta problemen ) lösas på exponentiell tid, vilket anses vara oacceptabelt ur praktisk synvinkel.

Historik

Frågan om beräkningskomplexitet ställdes förmodligen först av Kurt Gödel 1956 i ett brev till John von Neumann , där han frågade om ett problem (nu känt för att vara NP-komplett) kunde lösas i kvadratisk eller linjär tid. Samtidigt föreslog Gödel att om det finns en lösning kommer detta att tillåta datorer att lösa många matematiska problem [4] .

Frågan om klassjämlikhet togs upp först av Stephen Cook 1971 [ 5] och, oberoende, av Leonid Levin 1973 [ 6] .

I början av 2000-talet de flesta matematiker tror att dessa klasser inte är lika. Enligt en undersökning som gjordes 2002 bland 100 forskare [7] tror 61 personer att svaret är "inte lika", 9 - "lika", 22 hade svårt att svara och 8 menar att hypotesen inte kan härledas från nuvarande system av axiom , och därför kan det inte bevisas eller motbevisas.

Liksom andra välkända olösta matematiska problem kräver försök att lösa detta problem avsevärd ansträngning; felaktiga bevis på jämlikheten eller ojämlikheten i klasserna P och NP publiceras regelbundet (inte i den vetenskapliga litteraturen), vanligtvis av icke-professionella [8] .

Skyddssystem som antar olikheten mellan klasserna P och NP

Varje kryptosystem med offentlig nyckel är baserat på antagandet om förekomsten av envägsfunktioner och/eller den extrema varaktigheten av att lösa ett visst problem (till exempel för RSA- algoritmen är detta faktorisering av mycket stora tal).

För att skydda datorsystem från missbruk av tjänster ombeds den begärande parten att lösa ett problem som tar mycket tid att hitta en lösning och resultatet kontrolleras enkelt och snabbt av den serverande parten. Ett exempel på ett sådant anti -spam- skydd är Hashcash [9] -systemet , som använder en partiell inversions- hash när du skickar e-post.

Blockkedjor baserade på proof-of-work- teknik kräver att den resulterande hashsumman är mindre än målvärdet. Processen att söka efter den önskade hashsumman kräver dess upprepade omräkning med uppräkning av godtyckliga värden för den extra parametern (för mer information, se Mining ). Alla datorer i systemet spenderar en betydande tid på att söka efter en tillfredsställande hashsumma (till exempel i Bitcoin är detta i genomsnitt 10 minuter för var och en av gruvarbetarna ). För att kontrollera riktigheten av ett redan format block krävs endast en enda hashberäkning.

Liknande frågor

Se även

Anteckningar

  1. ↑ A. A. Razborov. P ?= NP eller problemet med uppräkning: en syn från 90-talet .
  2. ↑ A. H. Shen . Uppräkningsproblemet  // PostNauka .
  3. ↑ Stuart, 2015 , sid. 291.
  4. ↑ Hartmanis, Juris. Gödel, von Neumann och P = NP-problemet  (neopr.)  // Bulletin of the European Association for Theoretical Computer Science. - T. 38 . - S. 101-107 .
  5. ↑ Stephen Cook. Vikten av P kontra NP-frågan Arkiverad 9 juli 2011 på Wayback Machine .
  6. ↑ L. A. Levin. Universella uppräkningsproblem  // Problem med informationsöverföring. - 1973. - T. 9 , nr 3 . - S. 115-116 .
  7. ↑ William I. Gasarch. P=?NP-undersökningen  (neopr.)  // SIGACT News. - 2002. - T. 33 , nr 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
  8. ↑ Lenta.ru - Tidigare. Matematiker förlorade till slut tron ​​på att lösa millennieproblemet . Hämtad 26 augusti 2010. Arkiverad från originalet 30 augusti 2010.
  9. ↑ Hashcash - A Denial of Service Counter-Measure (2002)
  10. ↑ Razborov, 2016 , sid. 24.
  11. ↑ MIP* = RE: Landmark Data Science Bevis som orsakade en dominoeffekt i fysik och matematik / RUVDS.com Blog / Sudo Null IT News . Hämtad 24 december 2020. Arkiverad från originalet 12 maj 2021.
  12. ↑ [https://web.archive.org/web/20210119084755/https://arxiv.org/abs/2001.04383 Arkiverad 19 januari 2021 på Wayback Machine [2001.04383] MIP*=RE]

Litteratur

Länkar

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk