NP-hard
From Wikipedia, the free encyclopedia
NP-hard (după varianta în engleză, care vine de la „în timp nedeterminist polinomial dificilă) este, în teoria complexității, o proprietate definitorie a unei clase de probleme care sunt, în mod informal, „cel puțin la fel de grele ca cele mai grele probleme din NP”. În română, acestor probleme li se mai spune uneori și NP-dure sau NP-tari. Mai precis, o problemă H este NP-hard, atunci când toate problemele L din NP pot fi reduse în timp polinomial la H, adică: presupunând că o soluție pentru H ia 1 unitate de timp, putem folosi soluția lui H pentru a rezolva L în timp polinomial.[1][2] Ca urmare, găsirea unui algoritm în timp polinomial pentru a rezolva orice problemă NP-hard ar da algoritmi polinomiali pentru toate problemele din NP, ceea ce este puțin probabil, întrucât multe dintre ele sunt considerate dificile.[3]
O concepție greșită comună este că NP din „NP-hard” vine de la „nepolinomial” când, de fapt, înseamnă „probleme acceptabile Nedeterminist Polinomial”.[4] Deși se bănuiește că nu există niciun algoritm în timp polinomial pentru probleme NP-hard, acest lucru nu a fost demonstrat.[5] Mai mult decât atât, clasa P, în care toate problemele pot fi rezolvate în timp polinomial, este conținută în clasa NP.[6]