O problemă NP-hard este o problemă da/nu în care găsirea unei soluții este cel puțin la fel de dificilă ca și găsirea unei soluții pentru cea mai dificilă problemă a cărei soluție poate fi verificată rapid ca fiind adevărată. Unele probleme NP-hard sunt probleme în care o soluție funcțională poate fi verificată rapid (probleme NP), iar altele nu. Problemele NP-hard care sunt, de asemenea, probleme NP se încadrează într-o categorie numită NP-completă.
Un exemplu de problemă care este cel puțin la fel de greu de rezolvat ca orice altă problemă pentru care putem verifica rapid soluțiile, care este, de asemenea, rapid verificabilă (este atât NP-hard, cât și NP):
Un vânzător ambulant dorește să viziteze 100 de orașe cu mașina, începând și terminând călătoria acasă. El are o rezervă limitată de benzină, așa că poate parcurge în total doar 10 000 de kilometri. El vrea să știe dacă poate vizita toate orașele fără să rămână fără benzină.
Oamenii nu știu cum să rezolve această problemă mai repede decât să testeze fiecare răspuns posibil, dar dacă se găsește o soluție care îi permite vânzătorului să facă acest lucru, putem folosi un algoritm pentru a verifica dacă este adevărat. Această problemă mai este cunoscută și sub numele de "Travelling salesman problem".
Un exemplu de problemă care este cel puțin la fel de greu de rezolvat ca orice altă problemă pentru care putem verifica rapid soluțiile, dar care nu poate fi verificată rapid (este NP-hard, dar nu este NP):
dacă cineva începe un program care pur și simplu merge,
while(true){ continuă; }
și nu-l oprește niciodată, va funcționa la nesfârșit?
Nu există nicio modalitate cunoscută de a găsi o soluție la toate problemele de acest tip și nici acest lucru nu poate fi verificat.
Întrebări și răspunsuri
Î: Ce este o problemă NP-hard?
R: O problemă NP-hard este un tip de problemă matematică utilizată în informatică, care este o problemă de tip da/nu în care găsirea unei soluții este cel puțin la fel de dificilă ca și găsirea unei soluții pentru cea mai dificilă problemă a cărei soluție poate fi verificată rapid ca fiind adevărată.
Î: Se poate verifica rapid o soluție funcțională pentru toate problemele NP-hard?
R: Nu, numai unele probleme NP-hard, numite probleme NP, au soluții care pot fi verificate rapid.
Î: Cum se numește categoria problemelor NP-hard care sunt și probleme NP?
R: Problemele NP-hard care sunt, de asemenea, probleme NP se încadrează într-o categorie numită NP-complet.
Î: Toate problemele NP-hard sunt NP-complete?
R: Nu, nu toate problemele NP-hard sunt NP-complete. Doar cele care sunt și probleme NP se încadrează în această categorie.
Î: Sunt problemele NP-hard ușor de rezolvat?
R: Nu, problemele NP-hard nu sunt ușor de rezolvat. De fapt, găsirea unei soluții pentru acestea este cel puțin la fel de dificilă ca și găsirea unei soluții pentru cea mai grea problemă a cărei soluție poate fi rapid verificată ca fiind adevărată.
Î: Există avantaje în rezolvarea problemelor NP-hard?
R: Da, rezolvarea problemelor NP-hard poate oferi avantaje în diverse domenii, cum ar fi informatica, fizica și științele sociale, deoarece acestea pot necesita calcule și modelări complexe.
Î: Există cercetări în curs de desfășurare în domeniul rezolvării problemelor NP-hard?
R: Da, cercetarea în domeniul rezolvării problemelor NP-hard este în curs de desfășurare, deoarece aceste probleme continuă să fie relevante în diverse domenii, iar găsirea unor algoritmi și soluții eficiente poate avea implicații semnificative.
