NP-raske ja NP-kompleksne: määratlus ja näited
Sügav ülevaade NP-raske ja NP-kompleksne mõistetest: selged määratlused, intuitiivsed näited (nt rändmüüja), tähtsaimad kontseptsioonid ja algoritmide keerukus.
Määratlus
NP-raske (NP-hard) tähendab, et antud otsustusprobleem on vähemalt sama raske kui iga probleem, mille vastuseid saab kiirelt (polünominiaalses ajas) kontrollida. Täpsemalt öeldes: probleem B on NP-raskem, kui iga probleem A, mis kuulub klassi NP, on teisendatav probleemiks B polünominiaalses ajas (nn polünominiaalse aja many-one teisendus). See tähendab, et kui oskaksime kiiresti lahendada B-d, saaksime selle abil kiiresti lahendada ka kõik probleemid NP-s.
NP-kompleksne (NP-complete) on probleem, mis on samaaegselt NP-raske ja kuulub klassi NP. See tähendab, et tema lahendused on ka kontrollitavad polünominiaalses ajas (on olemas lühike „tõestus” ehk sertifikaat), ning iga teine NP-probleem teisendub temaks polünominiaalses ajas. Kui leiduks polünominiaalne algoritm ühegi NP-komplektse probleemi jaoks, tähendaks see, et P = NP ja kõik NP-probleemid saaksid lahendatud kiiresti.
Erinevus NP-raske ja NP-komplekse vahel
- NP — klass otsustusprobleemidest, mille jaoks saab antud vastuse (sertifikaadi) kontrollida polünominiaalses ajas.
- NP-kompleksne — kuulub NP-sse ja on samal ajal NP-raske.
- NP-raske — võib, aga ei pruugi kuuluda NP-sse; hulka kuuluvad ka probleemid, mis on „veel raskemad” (näiteks optimeerimisülesanded või otsustamatud probleemid).
Näited
NP-kompleksne näide (NP ja NP-raske):
Reisiv müügimees soovib külastada 100 linna, alustades ja lõpetades oma kodulinnas. Tema bensiinivarud on piiratud nii, et ta võib sõita kokku ainult 10 000 kilomeetrit. Küsimus on: kas leidub ringtee (Hamiltoni tsükkel), mis külastab kõiki linna ja mille pikkus ei ületa 10 000 km?
See on otsustusversioon tuntud rändmüüja probleemist (Traveling Salesman Problem, TSP). Selle otsustusvariandi puhul on võimalik kontrollida pakutud ringtee pikkust ja kehtivust polünominiaalses ajas — seega problem kuulub NP-sse — ning see on ka NP-raske, mistõttu on see NP-kompleksne. Inimesed ei tea üldiselt kiiremat (polünominiaalset) meetodit kõigi juhtumite jaoks kui kõigi võimalike ringteede ükshaaval kontrollimine, kuid kui keegi pakub ringteed, saab selle algoritmi abil kiiresti kontrollida.
NP-raske aga mitte NP (või otsustamatud / väga rasked) näited:
Mõned probleemid on tõsiselt raskemad või erineva olemusega: need ei ole otsustatavad või nende vastust ei ole võimalik üldiselt polünominiaalses ajas kontrollida. Näiteks küsimus „kas antud programm jookseb igavesti?” (näiteks programm, mis sisaldab silmust while(true){ continue; }) on seotud peatusprobleemiga ja üldjuhul otsustamatu. Selliste probleemide jaoks pole teadaolevat algoritmi, mis annaks õige vastuse kõigi võimalike sisendite korral, ning need ei kuulu NP-sse. Sellised probleemid võivad olla klassifitseeritavad erinevalt (nt otsustamatud), ja neid ei saa pidada NP-komplektseteks.
Lisaks: on olemas optimeerimisülesandeid (nt leida kõige lühem Hamiltoni tsükkel), mida tavaliselt nimetatakse NP-raskedeks: need ei ole otsustusprobleemid nagu NP, vaid nõuavad optimaalse lahendi leidmist ja selle kontrollimine võib tähendada lisaprobleeme—seetõttu ei pruugi need kuuluda NP-sse, kuigi NP-probleemid võivad neile polünominiaalselt vähenduda.
Mida see praktikas tähendab?
- Kui mõni NP-kompleksne probleem osutub polünominiaalselt lahendatavaks (kujutades seega P = NP), oleks see suure mõjuga: paljudele keerukatele ülesannetele, alates krüptograafiast kuni optimeerimise ja tõestuste automatiseerimiseni, muutuks lahendamine palju lihtsamaks.
- Praegu, kui polünominiaalset üldlahendust ei tunta, kasutatakse keerukate probleemide puhul praktilisi lähenemisi: heuristikad, umbkaudsed algoritmid (approximation), täpsed entkiiremad eksponentsiaalsed meetodid, ja piiratud juhtumite (erijuhtude) lahendamine.
- Paljude NP-raske klassi probleemide puhul piisab siiski headest lähendustest või erireeglitest, et saada praktiliselt kasulikke tulemusi suures osas reaalsest maailmast.
Kokkuvõte
NP-raske tähendab „vähemalt sama raske kui raskemad NP-probleemid” (polünominiaalse aja teisenduste suhtes). NP-kompleksne probleem on nii NP-raske kui ka NP-s: tema lahendused saab polünominiaalses ajas kontrollida ja kõik NP-probleemid vähenevad temaks. Paljude praktiliste keerukate ülesannete puhul on hea mõista, kas probleem kuulub NP-, NP-komplektsete või NP-raskete hulka, sest see juhib valikut sobivatest lahendusmeetoditest (täielikud algoritmid vs heuristikad/approximation jne).
Küsimused ja vastused
Küsimus: Mis on NP-raske probleem?
V: NP-raske probleem on arvutiteaduses kasutatav matemaatilise probleemi tüüp, mis on jah/ei probleem, mille lahenduse leidmine on vähemalt sama raske kui kõige raskema probleemi lahenduse leidmine, mille lahendust saab kiiresti kontrollida, kas see on tõene.
Küsimus: Kas kõikide NP-raskete probleemide puhul saab kiiresti kontrollida töötavat lahendust?
V: Ei, ainult mõnedele NP-rasketele probleemidele, mida nimetatakse NP-probleemideks, on võimalik kiiresti kontrollida lahendust.
K: Kuidas nimetatakse kategooriat NP-raskeid probleeme, mis on ühtlasi NP-probleemid?
V: NP-rasked probleemid, mis on ka NP-probleemid, kuuluvad kategooriasse, mida nimetatakse NP-komplektseks.
K: Kas kõik NP-rasked probleemid on NP-täielikud?
V: Ei, mitte kõik NP-rasked probleemid ei ole NP-täielikud. Ainult need, mis on ka NP-probleemid, kuuluvad sellesse kategooriasse.
K: Kas NP-raskeid probleeme on lihtne lahendada?
V: Ei, NP-raskeid probleeme ei ole lihtne lahendada. Tegelikult on nende lahenduse leidmine vähemalt sama raske kui kõige raskema probleemi lahenduse leidmine, mille lahenduse õigsust saab kiiresti kontrollida.
K: Kas NP-raskete probleemide lahendamisel on mingeid eeliseid?
V: Jah, NP-raskete probleemide lahendamine võib pakkuda eeliseid erinevates valdkondades, näiteks arvutiteaduses, füüsikas ja sotsiaalteadustes, kuna need võivad nõuda keerulisi arvutusi ja modelleerimist.
K: Kas NP-raskete probleemide lahendamise kohta käivad teadusuuringud?
V: Jah, NP-raskete probleemide lahendamise uurimine jätkub, sest need probleemid on jätkuvalt olulised eri valdkondades ning tõhusate algoritmide ja lahenduste leidmine võib avaldada märkimisväärset mõju.
Otsige