NP is die klas tale wat polinoomtydverifieerders het

/ / gepubliseer in Kuber sekuriteit, EITC/IS/CCTF Computational Complexity Theory Fundamentals, Kompleksiteit, Definisie van NP- en polinoom-verifieerbaarheid

Die klas NP, wat staan ​​vir "nie-deterministiese polinoomtyd," is 'n fundamentele konsep in berekeningskompleksiteitsteorie, 'n subveld van teoretiese rekenaarwetenskap. Om NP te verstaan, moet 'n mens eers die idee van besluitnemingsprobleme begryp, wat vrae is met 'n ja-of-nee-antwoord. 'n Taal in hierdie konteks verwys na 'n stel stringe oor een of ander alfabet, waar elke string 'n geval van 'n besluitprobleem kodeer.

Daar word gesê dat 'n taal (L) in NP is as daar 'n polinoom-tyd-verifieerder vir (L) bestaan. 'n Verifieerder is 'n deterministiese algoritme (V) wat twee insette neem: 'n instansie (x) en 'n sertifikaat (y). Die sertifikaat (y) staan ​​ook bekend as 'n "getuie" of "bewys." Die verifieerder (V) kontroleer of die sertifikaat (y) bevestig dat (x) aan die taal (L) behoort. Formeel is 'n taal (L) in NP as daar 'n polinoom-tyd-algoritme (V) en 'n polinoom (p(n)) bestaan ​​sodat daar vir elke string (x in L) 'n string (y) met ( |y|. leq p(|x|)) en (V(x, y) = 1). Omgekeerd, vir elke string (x notin L), is daar geen string (y) sodanig dat (V(x, y) = 1).

Om hierdie konsep toe te lig, oorweeg die bekende probleem van "Boolean satisfiability" (SAT). Die SAT-probleem vra of daar 'n toewysing van waarheidswaardes aan veranderlikes in 'n gegewe Boole-formule bestaan ​​sodat die formule na waar evalueer. Die SAT-probleem is in NP omdat, gegewe 'n Boole-formule ( phi ) en 'n toewysing ( alfa ) van waarheidswaardes aan sy veranderlikes, 'n mens in polinoomtyd kan verifieer of (alfa) voldoen aan (phi). Hier is die instansie ( x ) die Boole-formule ( phi ), en die sertifikaat ( y ) is die opdrag ( alfa ). Die verifieerder ( V ) kontroleer of ( alfa ) ( phi ) waar maak, wat in polinoomtyd gedoen kan word met betrekking tot die grootte van ( phi ).

Nog 'n illustratiewe voorbeeld is die "Hamiltonian Path"-probleem. Hierdie probleem vra of daar 'n pad in 'n gegewe grafiek bestaan ​​wat elke hoekpunt presies een keer besoek. Die Hamiltoniaanse Pad-probleem is ook in NP, want, gegewe 'n grafiek ( G ) en 'n volgorde van hoekpunte ( P ), kan 'n mens in polinoomtyd verifieer of ( P ) 'n Hamiltoniaanse pad in ( G ) is. In hierdie geval is die instansie ( x ) die grafiek ( G ), en die sertifikaat ( y ) is die volgorde van hoekpunte ( P ). Die verifieerder ( V ) kontroleer of ( P ) 'n Hamiltoniaanse pad vorm, wat in polinoomtyd gedoen kan word met betrekking tot die grootte van ( G ).

Die konsep van polinoom-tyd-verifieerbaarheid is belangrik omdat dit 'n manier bied om probleme te karakteriseer wat doeltreffend kontroleerbaar is, selfs al is die vind van die oplossing rekenaarmatig onuitvoerbaar. Dit lei tot die bekende vraag of ( P = NP ), wat vra of elke probleem waarvan die oplossing in polinoomtyd geverifieer kan word, ook in polinoomtyd opgelos kan word. Die klas ( P ) bestaan ​​uit besluitnemingsprobleme wat in polinoomtyd deur 'n deterministiese Turing-masjien opgelos kan word. Indien ( P = NP ), sou dit beteken dat elke probleem met 'n polinoom-tyd verifieerder ook 'n polinoom-tyd oplosser het. Hierdie vraag bly een van die belangrikste oop probleme in rekenaarwetenskap.

Een van die sleutel eienskappe van NP is dat dit gesluit is onder polinoom-tyd reduksies. 'n Polinoom-tyd-reduksie van 'n taal ( L_1 ) na 'n taal ( L_2 ) is 'n polinoom-tyd berekenbare funksie ( f ) sodanig dat ( x in L_1 ) as en slegs as ( f(x) in L_2 ). As daar 'n polinoom-tyd reduksie van ( L_1 ) na ( L_2 ) bestaan ​​en ( L_2 ) is in NP, dan is ( L_1 ) ook in NP. Hierdie eienskap is instrumenteel in die studie van NP-voltooidheid, wat die "moeilikste" probleme in NP identifiseer. 'n Probleem is NP-volledig as dit in NP is en elke probleem in NP kan in polinoomtyd tot dit gereduseer word. Die SAT-probleem was die eerste probleem wat as NP-volledig bewys is, en dit dien as 'n basis om die NP-volledigheid van ander probleme te bewys.

Om die konsep van polinoom-tyd verifieerbaarheid verder te illustreer, oorweeg die "Subset Sum" probleem. Hierdie probleem vra of daar 'n subset van 'n gegewe stel heelgetalle bestaan ​​wat tot 'n gespesifiseerde teikenwaarde optel. Die Subset Som-probleem is in NP omdat, gegewe 'n stel heelgetalle ( S ), 'n teikenwaarde ( t ), en 'n subset ( S' ) van ( S ), 'n mens in polinoomtyd kan verifieer of die som van die elemente in (S') is gelyk aan (t). Hier is die instansie ( x ) die paar ( (S, t) ), en die sertifikaat ( y ) is die subset ( S' ). Die verifieerder ( V ) kontroleer of die som van die elemente in ( S' ) gelyk is aan ( t ), wat in polinoomtyd gedoen kan word met betrekking tot die grootte van ( S ).

Die belangrikheid van polinoom-tyd-verifieerbaarheid strek verder as teoretiese oorwegings. In praktiese terme beteken dit dat vir probleme in NP, indien 'n voorgestelde oplossing (sertifikaat) verskaf word, dit doeltreffend nagegaan kan word. Dit het beduidende implikasies vir kriptografiese protokolle, optimaliseringsprobleme en verskeie velde waar die verifiëring van die korrektheid van 'n oplossing belangrik is.

Om op te som, die klas NP sluit besluitprobleme in waarvoor 'n voorgestelde oplossing in polinoomtyd deur 'n deterministiese algoritme geverifieer kan word. Hierdie konsep is grondliggend in rekenaarkompleksiteitsteorie en het diepgaande implikasies vir beide teoretiese en praktiese aspekte van rekenaarwetenskap. Die studie van NP, polinoom-tyd-verifieerbaarheid en verwante konsepte soos NP-volledigheid is steeds 'n lewendige en kritieke navorsingsgebied.

Ander onlangse vrae en antwoorde t.o.v Kompleksiteit:

Sien meer vrae en antwoorde in Complexity

Meer vrae en antwoorde:

Gemerk onder: , , , , ,