Wat zijn de verschillen tussen NP, NP-Complete en NP-Hard?
Ik ben op de hoogte van veel bronnen op internet. Ik zou graag je uitleg willen lezen, en de reden is dat ze misschien anders zijn dan wat er is, of dat er iets is waar ik niet van op de hoogte ben.
Antwoord 1, autoriteit 100%
Ik neem aan dat je op zoek bent naar intuïtieve definities, aangezien de technische definities behoorlijk wat tijd vergen om te begrijpen. Laten we allereerst een voorlopig concept onthouden om die definities te begrijpen.
- Besluitprobleem: een probleem met een ja of nee antwoord.
Laten we nu die complexiteitsklassen definiëren.
P
P is een complexiteitsklasse die de verzameling van alle beslissingsproblemen vertegenwoordigt die in polynomiale tijd kunnen worden opgelost.
Dat wil zeggen, gegeven een voorbeeld van het probleem, kan het antwoord ja of nee worden bepaald in polynomiale tijd.
Voorbeeld
Gegeven een verbonden grafiek G, kunnen de hoekpunten ervan worden gekleurd met twee kleuren zodat geen enkele rand monochromatisch is?
Algoritme: begin met een willekeurig hoekpunt, kleur het rood en al zijn buren blauw en ga verder. Stop als je geen hoekpunten meer hebt of als je gedwongen wordt om een rand te maken met beide eindpunten in dezelfde kleur.
NP
NP is een complexiteitsklasse die de verzameling van alle beslissingsproblemen vertegenwoordigt waarvoor de gevallen waarin het antwoord “ja” is, bewijzen hebben die in polynomiale tijd kunnen worden geverifieerd.
Dit betekent dat als iemand ons een exemplaar van het probleem geeft en een certificaat (soms een getuige genoemd) waarop het antwoord ja is, we kunnen controleren of het correct is in polynomiale tijd.
Voorbeeld
Integer factorisatie is in NP. Dit is het probleem dat gegeven gehele getallen n en m, is er een geheel getal f met 1 < f < m, zodat f n deelt (f is een kleine factor van n)?
Dit is een beslissingsprobleem omdat de antwoorden ja of nee zijn. Als iemand ons een instantie van het probleem geeft (zodat ze ons gehele getallen n en m geven) en een geheel getal f met 1 < f < m, en beweren dat f een factor is van n (het certificaat), kunnen we het antwoord in polynomiale tijd controleren door het uitvoeren van de verdeling n / f.
NP-Voltooid
NP-Complete is een complexiteitsklasse die de verzameling van alle problemen X in NP vertegenwoordigt waarvoor het mogelijk is om elk ander NP-probleem Y te reduceren tot X in polynomiale tijd.
Intuïtief betekent dit dat we Y snel kunnen oplossen als we weten hoe we X snel kunnen oplossen. Precies, Y is herleidbaar tot X, als er een polynomiaal tijdalgoritme f is om instanties Y van Y naar instanties x = f(y) van X in polynomiale tijd, met de eigenschap dat het antwoord op Y is ja, als en slechts als het antwoord op f(y) ja is.
Voorbeeld
3-SAT. Dit is het probleem waarbij we een voegwoord (AND’s) van disjuncties (OR’s) met 3 clausules krijgen, verklaringen van de vorm
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
waarbij elke x_vij een booleaanse variabele is of de ontkenning van een variabele uit een eindige vooraf gedefinieerde lijst (x_1, x_2, ... x_n).
Het kan worden aangetoond dat elk NP-probleem kan worden teruggebracht tot 3-SAT. Het bewijs hiervan is technisch en vereist het gebruik van de technische definitie van NP (gebaseerd op niet-deterministische Turingmachines). Dit staat bekend als de stelling van Cook.
Wat NP-volledige problemen belangrijk maakt, is dat als een deterministisch polynomiaal tijdalgoritme kan worden gevonden om een van hen op te lossen, elk NP-probleem oplosbaar is in polynomiale tijd (één probleem om ze allemaal te beheersen).
NP-hard
Intuïtief zijn dit de problemen die minstens zo moeilijk zijn als de NP-volledige problemen. Merk op dat NP-moeilijke problemen niet in NP hoeven te zitten, en ze geen beslissingsproblemen hoeven te zijn.
De precieze definitie hier is dat een probleem X NP-moeilijk is, als er een NP-compleet probleem is Y, zodat Y is herleidbaar tot X in polynomiale tijd.
Maar aangezien elk NP-compleet probleem kan worden herleid tot elk ander NP-compleet probleem in polynomiale tijd, kunnen alle NP-complete problemen worden herleid tot elk NP-hard probleem in polynomiale tijd. Als er dan een oplossing is voor één NP-moeilijk probleem in polynomiale tijd, is er een oplossing voor alle NP-problemen in polynomiale tijd.
Voorbeeld
Het stopprobleem is een moeilijk NP-probleem. Dit is het probleem dat gegeven een programma P en invoer I, zal het stoppen? Dit is een beslissingsprobleem, maar het is niet in NP. Het is duidelijk dat elk NP-compleet probleem tot dit probleem kan worden teruggebracht. Een ander voorbeeld: elk NP-compleet probleem is NP-moeilijk.
Mijn favoriete NP-complete probleem is het Mijnenveger-probleem.
P = NP
Dit is het bekendste probleem in de informatica en een van de belangrijkste openstaande vragen in de wiskundige wetenschappen. Het Clay Institute biedt zelfs een miljoen dollar voor een oplossing voor het probleem (Stephen Cook’s write-up op de Clay-website is redelijk goed ).
Het is duidelijk dat P een deelverzameling is van NP. De open vraag is of NP-problemen al dan niet deterministische polynomiale tijdoplossingen hebben. Er wordt grotendeels aangenomen dat ze dat niet doen. Hier is een uitstekend recent artikel over het laatste (en het belang) van het P = NP-probleem: De status van het P versus NP-probleem.
Het beste boek over dit onderwerp is Computers and Intractability van Garey en Johnson .
Antwoord 2, autoriteit 18%
Ik heb rondgekeken en veel lange uitleg gezien.
Hier is een kleine grafiek die handig kan zijn om samen te vatten:
Merk op hoe de moeilijkheidsgraad van boven naar beneden toeneemt: elke NP kan worden teruggebracht tot NP-Compleet en elke NP-Complete kan worden teruggebracht tot NP-Hard, all-in P (polynomiale) tijd.
Als je een moeilijkere klasse van problemen in P-tijd kunt oplossen, betekent dat dat je hebt gevonden hoe je alle eenvoudigere problemen in P-tijd kunt oplossen (bijvoorbeeld door P = NP te bewijzen, als je weet hoe je een NP- Voltooi het probleem in P-tijd).
_______________________________________________________________________ | Probleemtype | Verifieerbaar in P-tijd | Oplosbaar in P-tijd | Toenemende moeilijkheidsgraad ____________________________________________________________| | | P | Ja | Ja | | | NP | Ja | Ja of Nee * | | | NP-Volledig | Ja | Onbekend | | | NP-Hard | Ja of Nee ** | Onbekend *** | | ____________________________________________________________________________ V
Opmerkingen over Yes of No items:
- * Een NP-probleem dat ook P is, is oplosbaar in P-tijd.
- ** Een NP-Hard probleem dat ook NP-Compleet is, is verifieerbaar in P-tijd.
- *** NP-Complete problemen (die allemaal een subset van NP-hard vormen) kunnen zijn. De rest van NP moeilijk is dat niet.
Ik vond dit diagram ook best handig om te zien hoe deze typen corresponderen met elkaar (let meer op de linkerhelft van het diagram).
Antwoord 3, autoriteit 6%
P (Polynomiale Tijd): Zoals de naam al doet vermoeden, zijn dit de problemen die in polynomiale tijd kunnen worden opgelost.
NP (niet-deterministische-polynomiale tijd): Dit zijn de beslissingsproblemen die kunnen worden geverifieerd in polynomiale tijd. Dat betekent dat als ik beweer dat er een polynomiale tijdoplossing is voor een bepaald probleem, je mij vraagt om het te bewijzen. Dan zal ik je een bewijs geven dat je gemakkelijk kunt verifiëren in polynomiale tijd. Dit soort problemen worden NP-problemen genoemd. Merk op dat we het hier niet hebben over de vraag of er een polynomiale tijdoplossing voor dit probleem is of niet. Maar we hebben het over het verifiëren van de oplossing voor een bepaald probleem in polynomiale tijd.
NP-Hard: deze zijn minstens zo moeilijk als de moeilijkste problemen in NP. Als we deze problemen in polynomiale tijd kunnen oplossen, kunnen we elk mogelijk bestaand NP-probleem oplossen. Merk op dat deze problemen niet noodzakelijk NP-problemen zijn. Dat betekent dat we de oplossing voor deze problemen wel/niet kunnen verifiëren in polynomiale tijd.
NP-Compleet: dit zijn de problemen die zowel NP als NP-Hard zijn. Dat betekent dat als we deze problemen kunnen oplossen, we elk ander NP-probleem kunnen oplossen en de oplossingen voor deze problemen kunnen worden geverifieerd in polynomiale tijd.
Antwoord 4, autoriteit 5%
Dit is een zeer informeel antwoord op de gestelde vraag.
Kan 3233 worden geschreven als het product van twee andere getallen groter dan 1? Is er een manier om een pad rond alle Zeven Bruggen van Konigsberg te bewandelen zonder twee keer een brug nemen? Dit zijn voorbeelden van vragen met een gemeenschappelijk kenmerk. Het is misschien niet voor de hand liggend hoe je het antwoord efficiënt kunt bepalen, maar als het antwoord ‘ja’ is, dan is er een kort en snel te controleren bewijs. In het eerste geval een niet-triviale factorisatie van 51; in de tweede een route om over de bruggen te lopen (passend bij de beperkingen).
Een beslissingsprobleem is een verzameling vragen met ja of nee antwoorden die slechts in één parameter variëren. Zeg het probleem COMPOSITE={“Is n samengesteld”: n is een geheel getal} of EULERPATH={“Heeft de grafiek G een Euler pad?”: G is een eindige grafiek}.
Sommige beslissingsproblemen lenen zich nu voor efficiënte, zo niet voor de hand liggende algoritmen. Euler ontdekte meer dan 250 jaar geleden een efficiënt algoritme voor problemen zoals de “Zeven Bruggen van Konigsberg”.
Aan de andere kant is het voor veel beslissingsproblemen niet duidelijk hoe je het antwoord krijgt — maar als je wat extra informatie weet, is het duidelijk hoe je kunt bewijzen dat je het juiste antwoord hebt. SAMENSTELLING is als volgt: proefdeling is het voor de hand liggende algoritme, en het is traag: om een getal van 10 cijfers te ontbinden, moet je zoiets als 100.000 mogelijke delers proberen. Maar als iemand je bijvoorbeeld heeft verteld dat 61 een deler is van 3233, is een eenvoudige staartdeling een efficiënte manier om te zien of ze correct zijn.
De complexiteitsklasse NP is de klasse van beslissingsproblemen waarbij de ‘ja’-antwoorden kort zijn, snel te controleren bewijzen. Zoals COMPOSIET. Een belangrijk punt is dat deze definitie niets zegt over hoe moeilijk het probleem is. Als je een correcte, efficiënte manier hebt om een beslissingsprobleem op te lossen, is het voldoende om de stappen in de oplossing op te schrijven.
Het onderzoek naar algoritmen gaat door en er worden voortdurend nieuwe slimme algoritmen gemaakt. Een probleem dat u vandaag misschien niet efficiënt weet op te lossen, kan morgen een efficiënte (zo niet voor de hand liggende) oplossing blijken te zijn. In feite duurde het tot 2002 om een efficiënte oplossing te vinden voor COMPOSITE! Met al deze vorderingen moet je je echt afvragen: is dit stukje over het hebben van korte bewijzen slechts een illusie? Misschien heeft elk beslissingsprobleem dat zich leent voor efficiënte bewijzen een efficiënte oplossing? Niemand weet het.
Misschien kwam de grootste bijdrage aan dit veld met de ontdekking van een eigenaardige klasse van NP-problemen. Door te spelen met circuitmodellen voor berekeningen, vond Stephen Cook een beslissingsprobleem van de NP-variant dat aantoonbaar net zo moeilijk of moeilijker was dan elk ander NP-probleem. Een efficiënte oplossing voor het booleaanse verzadigingsprobleem zou kunnen worden gebruikt om een efficiënt oplossing voor elk ander probleem in NP. Kort daarna toonde Richard Karp aan dat een aantal andere beslissingsproblemen hetzelfde doel konden dienen. Deze problemen, in zekere zin de “moeilijkste” problemen in NP, werden bekend als NP-complete problemen.
Natuurlijk is NP slechts een klasse van beslissingsproblemen. Veel problemen worden natuurlijk niet op deze manier uitgedrukt: “vind de factoren van N”, “vind het kortste pad in de grafiek G dat elk hoekpunt bezoekt”, “geef een reeks variabele toewijzingen die de volgende booleaanse uitdrukking waar maken”. Hoewel men informeel kan praten over sommige van dergelijke problemen die “in NP” zijn, heeft dat technisch gezien niet veel zin – het zijn geen beslissingsproblemen. Sommige van deze problemen kunnen zelfs dezelfde kracht hebben als een NP-compleet probleem: een efficiënte oplossing voor deze (niet-beslissings)problemen zou direct leiden tot een efficiënte oplossing voor elk NP-probleem. Een probleem als dit wordt NP-hard genoemd.
Antwoord 5, autoriteit 4%
Naast de andere geweldige antwoorden, is hier het typische schema gebruiken mensen om het verschil tussen NP, NP-Complete en NP-Hard aan te tonen:
Antwoord 6, autoriteit 3%
De gemakkelijkste manier om P v. NP en dergelijke uit te leggen zonder in technische details te treden, is door “woordproblemen” te vergelijken met “meerkeuzeproblemen”.
Als je een “woordprobleem” probeert op te lossen, moet je de oplossing helemaal opnieuw vinden.
Wanneer u een “meerkeuzeprobleem” probeert op te lossen, heeft u de keuze: of los het op zoals u een “woordprobleem” zou doen, of probeer elk van de aan u gegeven antwoorden in te vullen en kies het kandidaat-antwoord dat past.
Het komt vaak voor dat een “meerkeuzeprobleem” veel gemakkelijker is dan het bijbehorende “woordprobleem”: het vervangen van de antwoorden van de kandidaat en het controleren of ze passen, kan aanzienlijk minder inspanning vergen dan het helemaal opnieuw vinden van het juiste antwoord.
Als we het er nu over eens zijn dat de inspanning die polynomiale tijd kost “gemakkelijk” is, dan zou de klasse P bestaan uit “eenvoudige woordproblemen”, en de klasse NP zou bestaan uit “gemakkelijke meerkeuzeproblemen”.
De essentie van P v. NP is de vraag: “Zijn er eenvoudige meerkeuzeproblemen die niet zo eenvoudig zijn als woordproblemen”? Dat wil zeggen, zijn er problemen waarvoor het gemakkelijk is om de geldigheid van een bepaald antwoord te verifiëren, maar het is moeilijk om dat antwoord helemaal opnieuw te vinden?
Nu we intuïtief begrijpen wat NP is, moeten we onze intuïtie uitdagen. Het blijkt dat er “meerkeuzeproblemen” zijn die in zekere zin het moeilijkst van allemaal zijn: als men een oplossing zou vinden voor een van die “moeilijkste van allemaal” problemen zou men een oplossing kunnen vinden voor ALLE NP problemen! Toen Cook dit 40 jaar geleden ontdekte, kwam het als een complete verrassing. Deze “moeilijkste van allemaal” problemen staan bekend als NP-hard. Als u een “woordprobleemoplossing” voor een van hen vindt, vindt u automatisch een “woordprobleemoplossing” voor elk “eenvoudig meerkeuzeprobleem”!
Ten slotte zijn NP-complete problemen problemen die tegelijkertijd NP en NP-moeilijk zijn. In navolging van onze analogie zijn ze tegelijkertijd “eenvoudig als meerkeuzeproblemen” en “de moeilijkste van allemaal als woordproblemen”.
Antwoord 7
Ik denk dat we het veel beknopter kunnen beantwoorden. Ik heb een gerelateerde vraag, en mijn antwoord van daaruit kopiëren
Maar eerst is een NP-hard probleem een probleem waarvoor we niet kunnen bewijzen dat er een polynomiale tijdoplossing bestaat. NP-hardheid van een “probleem-P” wordt meestal bewezen door een reeds bewezen NP-hard probleem om te zetten naar het “probleem-P” in polynomiale tijd.
Om de rest van de vraag te beantwoorden, moet je eerst begrijpen welke NP-harde problemen ook NP-compleet zijn. Als een NP-hard probleem tot de verzameling NP behoort, dan is het NP-compleet. Om tot set NP te behoren, moet een probleem zijn
(i) een beslissingsprobleem,
(ii) het aantal oplossingen voor het probleem moet eindig zijn en elke oplossing moet een polynoomlengte hebben, en
(iii) gegeven een polynoomlengte-oplossing, zouden we moeten kunnen zeggen of het antwoord op het probleem ja/nee isHet is nu gemakkelijk in te zien dat er veel NP-moeilijke problemen kunnen zijn die niet tot de set NP behoren en moeilijker op te lossen zijn. Als intuïtief voorbeeld: de optimalisatieversie van handelsreiziger waarbij we een echt schema moeten vinden, is moeilijker dan de beslissingsversie van handelsreiziger waarbij we alleen moeten bepalen of een schema met lengte <= k bestaat of niet.
Antwoord 8
NP-complete problemen zijn die problemen die zowel NP-Hard zijn als in de complexiteitsklasse NP. Om aan te tonen dat een bepaald probleem NP-compleet is, moet je dus aantonen dat het probleem zowel in NP zit als dat het NP-moeilijk is.
Problemen die in de NP-complexiteitsklasse vallen, kunnen niet-deterministisch worden opgelost in polynomiale tijd en een mogelijke oplossing (d.w.z. een certificaat) voor een probleem in NP kan worden geverifieerd op correctheid in polynomiale tijd.
Een voorbeeld van een niet-deterministische oplossing voor het k-clique-probleem zou zoiets zijn als:
1) selecteer willekeurig k knopen uit een grafiek
2) controleer of deze k-knooppunten een kliek vormen.
De bovenstaande strategie is polynoom in de grootte van de invoergrafiek en daarom is het k-kliekprobleem in NP.
Merk op dat alle problemen die deterministisch oplosbaar zijn in polynomiale tijd ook in NP zijn.
Aantonen dat een probleem NP-hard is, houdt doorgaans een reductie in van een ander NP-hard probleem naar uw probleem met behulp van een polynomiale tijdtoewijzing: http://en.wikipedia.org/wiki/Reduction_(complexity)
Antwoord 9
Er zijn echt mooie antwoorden op deze specifieke vraag, dus het heeft geen zin om mijn eigen uitleg te schrijven. Dus ik zal proberen bij te dragen met een uitstekende bron over verschillende klassen van computationele complexiteit.
Voor iemand die denkt dat computationele complexiteit alleen over P en NP gaat, hier is de meest uitgebreide bron over verschillende computationele complexiteitsproblemen . Afgezien van de problemen die door OP werden gesteld, somde het ongeveer 500 verschillende klassen van rekenproblemen op met mooie beschrijvingen en ook de lijst van fundamentele onderzoekspapers die de klasse beschrijven.
Antwoord 10
Vind een interessante definitie:
Antwoord 11
Zoals ik het begrijp, is een np-hard probleem niet “moeilijker” dan een np-complete probleem. In feite is elk np-complete probleem per definitie:
- in NP
- np-hard
— Inleiding. naar algoritmen (3ed) door Cormen, Leiserson, Rivest en Stein, pg 1069
Voorwaarde 1. en 2. vertaald naar het Engels:
- Taal L is in NP, en
- Elke NP-taal is polynomiale tijd herleidbaar tot taal L.