Ligestilling af klasserne P og NP

Spørgsmålet om ligheden af ​​kompleksitetsklasserne P og NP (også kendt i russiske kilder som opregningsproblemet [1] [2] ) har været et af de centrale åbne problemer i teorien om algoritmer i mere end tre årtier. Hvis der gives et bekræftende svar på det, vil det betyde, at det teoretisk er muligt at løse mange komplekse problemer meget hurtigere end nu.

Forholdet mellem klasserne P og NP behandles i en gren af ​​algoritmeteorien kaldet beregningskompleksitetsteori . Den studerer de ressourcer, der er nødvendige for at løse et eller andet problem. De mest almindelige ressourcer er tid (hvor mange trin der skal tages) og hukommelse (hvor meget hukommelse det tager at fuldføre en opgave).

Problemet med ligheden mellem klasserne P og NP er et af de syv årtusindproblemer , som Clay Mathematical Institute tildelte en pris på en million amerikanske dollars for .

Ordlyd

Løst sagt er lighedsproblemet P = NP som følger: hvis et positivt svar på et spørgsmål kan kontrolleres ret hurtigt (i polynomiumtid ), så er det rigtigt, at svaret på dette spørgsmål kan findes ret hurtigt (også i polynomium ) tid og brug af polynomiel hukommelse )? Med andre ord, er det virkelig ikke nemmere at tjekke løsningen af ​​problemet end at finde det? [3]

Er det f.eks. rigtigt, at der blandt tallene { −2 , −3 , 15 , 14 , 7 , −10 , …} er sådanne, at deres sum er lig med 0 ( subset sum problem )? Svaret er ja , fordi −2 −3 + 15 −10 = 0 let verificeres ved nogle få tilføjelser (den information, der er nødvendig for at bekræfte et positivt svar, kaldes et certifikat ). Følger det, at det er lige så nemt at hente disse tal? Er det lige så nemt at tjekke et certifikat som at finde det? Det ser ud til, at det er sværere at hente tal, men det er ikke blevet bevist.

Fra definitionen af ​​klasserne P og NP følger umiddelbart følgen: . Der vides dog intet indtil videre om strengheden af ​​denne inklusion, det vil sige om der er et problem, der ligger i NP , men ikke ligger i P. Hvis et sådant problem ikke eksisterer, så kan alle problemer, der tilhører klassen NP , løses i polynomiel tid, hvilket lover en enorm fordel i beregningshastigheden. Nu kan de mest komplekse problemer fra NP -klassen (de såkaldte NP - komplette problemer ) løses i eksponentiel tid, hvilket anses for uacceptabelt fra et praktisk synspunkt.

Historie

Spørgsmålet om beregningsmæssig kompleksitet blev sandsynligvis først stillet af Kurt Gödel i 1956 i et brev til John von Neumann , hvor han spurgte, om et problem (nu kendt for at være NP-komplet) kunne løses i kvadratisk eller lineær tid. Samtidig foreslog Gödel, at hvis der findes en løsning, så vil dette gøre det muligt for computere at løse mange matematiske problemer [4] .

Spørgsmålet om klasselighed blev først rejst af Stephen Cook i 1971 [5] og uafhængigt af Leonid Levin i 1973 [6] .

I begyndelsen af ​​2000-tallet de fleste matematikere mener, at disse klasser ikke er lige. Ifølge en undersøgelse foretaget i 2002 blandt 100 videnskabsmænd [7] mener 61 personer, at svaret er "ikke lige", 9 - "lige", 22 havde svært ved at svare og 8 mener, at hypotesen ikke kan udledes af den nuværende system af aksiomer , og det kan derfor ikke bevises eller modbevises.

Ligesom andre velkendte uløste matematiske problemer kræver forsøg på at løse dette problem en betydelig indsats; fejlagtige beviser for ligheden eller uligheden i klasserne P og NP offentliggøres regelmæssigt (ikke i den videnskabelige litteratur), normalt af ikke-professionelle [8] .

Beskyttelsessystemer, der antager uligheden mellem klasserne P og NP

Ethvert offentligt nøglekryptosystem er baseret på antagelsen om eksistensen af ​​envejsfunktioner og/eller den ekstreme varighed af løsningen af ​​et bestemt problem (f.eks. for RSA -algoritmen er dette faktoriseringen af ​​meget store tal).

For at beskytte computersystemer mod misbrug af tjenester, bliver rekvirenten bedt om at løse et problem, der tager lang tid at finde en løsning, og resultatet bliver nemt og hurtigt tjekket af den serverende part. Et eksempel på en sådan anti - spam -beskyttelse er Hashcash [9] -systemet , som bruger en delvis inversion- hash ved afsendelse af e-mail.

Blockchains baseret på proof-of-work- teknologi kræver, at den resulterende hash-sum er mindre end målværdien. Processen med at søge efter den ønskede hash-sum kræver dens gentagne genberegning med opregning af vilkårlige værdier af den ekstra parameter (for flere detaljer, se Mining ). Alle computere i systemet bruger en betydelig mængde tid på at søge efter én tilfredsstillende hash-sum (for eksempel i Bitcoin er dette et gennemsnit på 10 minutter for hver af minearbejderne ). For at kontrollere rigtigheden af ​​en allerede dannet blok kræves kun en enkelt hash-beregning.

Lignende problemer

Se også

Noter

  1. ↑ A. A. Razborov. P ?= NP eller opregningsproblemet: et syn fra 90'erne .
  2. ↑ A. H. Shen . Optællingsproblemet  // PostNauka .
  3. ↑ Stuart, 2015 , s. 291.
  4. ↑ Hartmanis, Juris. Gödel, von Neumann og P = NP-problemet  (neopr.)  // Bulletin of the European Association for Theoretical Computer Science. - T. 38 . - S. 101-107 .
  5. ↑ Stephen Cook. Vigtigheden af ​​P versus NP-spørgsmålet Arkiveret 9. juli 2011 på Wayback Machine .
  6. ↑ L. A. Levin. Problemer med universel opregning  // Problemer med informationsoverførsel. - 1973. - T. 9 , nr. 3 . - S. 115-116 .
  7. ↑ William I. Gasarch. P=?NP-afstemningen  (neopr.)  // SIGACT News. - 2002. - T. 33 , nr. 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
  8. ↑ Lenta.ru - Past. Matematikere mistede endelig troen på at løse årtusindskiftets problem . Hentet 26. august 2010. Arkiveret fra originalen 30. august 2010.
  9. ↑ Hashcash - A Denial of Service Counter-Measure (2002)
  10. ↑ Razborov, 2016 , s. 24.
  11. ↑ MIP* = RE: Landmark Computer Science Proof That Caused a Domino Effect in Physics and Mathematics / RUVDS.com Blog / Sudo Null IT News . Hentet 24. december 2020. Arkiveret fra originalen 12. maj 2021.
  12. ↑ [https://web.archive.org/web/20210119084755/https://arxiv.org/abs/2001.04383 Arkiveret 19. januar 2021 på Wayback Machine [2001.04383] MIP*=RE]

Litteratur

Links

  Gå til Wikidata-elementet  Ordbøger og encyklopædier