NP-karedus
NP-raske probleem on jah/ei probleem, mille lahendamine on vähemalt sama raske kui kõige raskema probleemi lahendamine, mille lahendust saab kiiresti kontrollida, kas see on tõene. Mõned NP-rasked probleemid on sellised, mille toimivat lahendust saab kiiresti kontrollida (NP-probleemid), mõned aga mitte. NP-rasked probleemid, mis on ka NP-probleemid, kuuluvad kategooriasse, mida nimetatakse NP-komplektseks.
Näide probleemist, mida on vähemalt sama raske lahendada kui mis tahes muud probleemi, mille lahendusi me saame kiiresti kontrollida ja mis on ka kiiresti kontrollitav (see on nii NP-raske kui ka NP):
Reisiv müügimees soovib külastada 100 linna, alustades ja lõpetades oma reisi kodus. Tema bensiinivarud on piiratud, nii et ta saab sõita kokku ainult 10 000 kilomeetrit. Ta tahab teada, kas ta suudab külastada kõiki linnu, ilma et bensiin otsa saaks.
Inimesed ei tea, kuidas seda probleemi kiiremini lahendada kui iga võimaliku vastuse testimine, kuid kui on leitud lahendus, mis võimaldab müüja seda teha, saame algoritmi abil kontrollida, et see on tõene. Seda probleemi tuntakse ka kui rändmüüja probleemi.
Näide probleemist, mida on vähemalt sama raske lahendada kui mis tahes muud probleemi, mille lahendusi me saame kiiresti kontrollida, kuid mida ei saa kiiresti kontrollida (see on NP-raske, kuid ei ole NP):
kui keegi alustab programmi, mis lihtsalt läheb,
while(true){ continue; }ja ei peata seda kunagi, kas see jookseb igavesti?
Kõigile sellistele probleemidele ei ole teadaolevalt võimalik leida lahendust ja seda ei saa ka kontrollida.
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.
