Egalitatea claselor P și NP

Problema egalității claselor de complexitate P și NP (cunoscută și în sursele ruse ca problema de enumerare [1] [2] ) a fost una dintre problemele centrale deschise în teoria algoritmilor de mai bine de trei decenii. Dacă i se dă un răspuns afirmativ, aceasta va însemna că teoretic este posibil să se rezolve multe probleme complexe mult mai rapid decât acum.

Relația dintre clasele P și NP este tratată într-o ramură a teoriei algoritmilor numită teoria complexității computaționale . Studiază resursele necesare pentru a rezolva o problemă. Cele mai comune resurse sunt timpul (câți pași trebuie să faceți) și memoria (câtă memorie este nevoie pentru a finaliza o sarcină).

Problema egalității claselor P și NP este una dintre cele șapte probleme ale mileniului pentru care Institutul de Matematică Clay a acordat un premiu de un milion de dolari SUA .

Formulare

Vag vorbind, problema egalității P = NP este următoarea: dacă un răspuns pozitiv la o întrebare poate fi verificat destul de repede (în timp polinomial ), atunci este adevărat că răspunsul la această întrebare poate fi găsit destul de repede (și în polinom ). timp și folosind memoria polinomială )? Cu alte cuvinte, nu este chiar mai ușor să verifici soluția problemei decât să o găsești? [3]

De exemplu, este adevărat că printre numerele { −2 , −3 , 15 , 14 , 7 , −10 , …} există astfel încât suma lor este egală cu 0 ( problema sumei submulțimii )? Răspunsul este da , deoarece −2 −3 + 15 −10 = 0 este ușor de verificat prin câteva completări (informația necesară pentru a verifica un răspuns pozitiv se numește certificat ). Rezultă că este la fel de ușor să ridici aceste numere? Verificarea unui certificat este la fel de ușoară ca și găsirea acestuia? Se pare că adunarea numerelor este mai dificilă, dar acest lucru nu a fost dovedit.

Din definiţia claselor P şi NP rezultă imediat corolarul: . Cu toate acestea, până acum nu se știe nimic despre strictețea acestei includeri, adică dacă există o problemă care se află în NP , dar nu se află în P. Dacă o astfel de problemă nu există, atunci toate problemele aparținând clasei NP pot fi rezolvate în timp polinomial, ceea ce promite un beneficiu imens în viteza de calcul. Acum cele mai complexe probleme din clasa NP (așa-numitele NP - probleme complete ) pot fi rezolvate în timp exponențial, ceea ce este considerat inacceptabil din punct de vedere practic.

Istorie

Problema complexității computaționale a fost probabil pusă pentru prima dată de Kurt Gödel în 1956 într-o scrisoare către John von Neumann , unde a întrebat dacă o problemă (acum cunoscută ca fiind NP-completă) poate fi rezolvată în timp patratic sau liniar . În același timp, Gödel a sugerat că, dacă există o soluție, atunci aceasta va permite computerelor să rezolve multe probleme matematice [4] .

Problema egalității de clasă a fost pusă pentru prima dată de Stephen Cook în 1971 [5] și, independent, de Leonid Levin în 1973 [6] .

La începutul anilor 2000 majoritatea matematicienilor cred că aceste clase nu sunt egale. Conform unui sondaj efectuat în 2002 în rândul a 100 de oameni de știință, [7] 61 de oameni cred că răspunsul este „nu este egal”, 9 – „egal”, 22 au găsit greu să răspundă și 8 cred că ipoteza nu este dedusabilă din actuala sistem de axiome și, astfel, nu poate fi dovedit sau infirmat.

Ca și alte probleme matematice nerezolvate bine-cunoscute, încercările de a rezolva această problemă implică un efort considerabil; dovezile eronate ale egalității sau inegalității claselor P și NP sunt publicate în mod regulat (nu în literatura științifică), de obicei de către neprofesioniști [8] .

Sisteme de protecție care presupun inegalitatea claselor P și NP

Orice criptosistem cu cheie publică se bazează pe presupunerea existenței unor funcții unidirecționale și/sau a duratei extreme de rezolvare a unei anumite probleme (de exemplu, pentru algoritmul RSA , aceasta este factorizarea unor numere foarte mari).

Pentru a proteja sistemele informatice de abuzul de servicii, părții solicitante i se cere să rezolve o problemă care necesită mult timp pentru a găsi o soluție, iar rezultatul este ușor și rapid verificat de către partea care servește. Un exemplu de astfel de protecție anti -spam este sistemul Hashcash [9] , care utilizează un hash de inversare parțială atunci când trimite e-mail.

Blockchain -urile bazate pe tehnologia proof -of-work necesită ca suma hash rezultată să fie mai mică decât valoarea țintă. Procesul de căutare a sumei hash dorite necesită recalcularea repetată a acesteia cu enumerarea valorilor arbitrare ale parametrului suplimentar (pentru mai multe detalii, vezi Mining ). Toate computerele din sistem petrec o cantitate semnificativă de timp căutând o sumă hash satisfăcătoare (de exemplu, în Bitcoin , aceasta este o medie de 10 minute pentru fiecare dintre mineri ). Pentru a verifica corectitudinea unui bloc deja format, este necesar doar un singur calcul hash.

Probleme similare

• O problemă similară există în teoria complexității algebrice pentru clasele VP și VNP [10] . Momentan aceasta problema nu a fost rezolvata.

• În 2020, a fost obținută o dovadă a egalității claselor REși MIP* [11] [12] .

Vezi și

• forta bruta
• probleme matematice deschise

Note

1. ↑ A. A. Razborov. P ?= NP sau problema enumerarii: o vedere din anii '90 .
2. ↑ A. H. Shen . Problema enumerarii  // PostNauka .
3. ↑ Stuart, 2015 , p. 291.
4. ↑ Hartmanis, Juris. Gödel, von Neumann și problema P = NP  (neopr.)  // Buletinul Asociației Europene pentru Informatică Teoretică. - T. 38 . - S. 101-107 .
5. ↑ Stephen Cook. Importanța întrebării P versus NP Arhivat la 9 iulie 2011 la Wayback Machine .
6. ↑ L. A. Levin. Probleme de enumerare universală  // Probleme de transmitere a informaţiei. - 1973. - T. 9 , nr 3 . - S. 115-116 . (Rusă)
7. ↑ William I. Gasarch. Sondajul P=?NP  (neopr.)  // Ştiri SIGACT. - 2002. - T. 33 , nr 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
8. ↑ Lenta.ru - Trecut. Matematicienii și-au pierdut în cele din urmă încrederea în rezolvarea problemei mileniului . Preluat la 26 august 2010. Arhivat din original la 30 august 2010. (nedefinit)
9. ↑ Hashcash - A Denial of Service Counter-Measure (2002)
10. ↑ Razborov, 2016 , p. 24.
11. ↑ MIP* = RE: Dovada de referință în domeniul informaticii care a provocat un efect de domino în fizică și matematică / RUVDS.com Blog / Sudo Null IT News . Preluat la 24 decembrie 2020. Arhivat din original la 12 mai 2021. (nedefinit)
12. ↑ [https://web.archive.org/web/20210119084755/https://arxiv.org/abs/2001.04383 Arhivat 19 ianuarie 2021 la Wayback Machine [2001.04383] MIP*=RE]

Literatură

• Ian Stewart . Cele mai mari probleme de matematică. — M. : Alpina non-fiction, 2015. — 460 p. - ISBN 978-5-91671-318-3 .
• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .
• Razborov A. A. Complexitatea algebrică. — M .: MTsNMO , 2016. — 32 p. - ISBN 978-5-4439-1032-1 .

Link -uri

• S. Cook Descrierea oficială a problemei  (ing.)
• S. Nikolenko "P=?NP" . Computerra, 2006.
• N. P. Varnovsky. Problema P=? NP, clase de complexitate și criptografie . 2005.
• Pritykin Yu. L. Care este problema lui P vs. NP?  // VIII Școala de vară „Matematică modernă”. — Dubna, 2008.
• Gerhard J. Woeginger. Pagina P-versus-NP . (eng.) Lista de link-uri către „soluții” propuse la această problemă până în 2016. Unii dintre ei susțin egalitatea lui P și NP , alții - opusul.
• Scott Aaronson. Motive pentru a crede că P!=NP
• Scott Aaronson . — Recenzia din 2017.

Dicționare și enciclopedii	Britannica (online) Britannica (online)