|
NP-hardness (''n''on-deterministic ''p''olynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". More precisely, a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''. As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard. A common mistake is thinking that the ''NP'' in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for NP-hard problems, this has never been proven. Moreover, the class NP also contains all problems which can be solved in polynomial time. == Definition == A decision problem ''H'' is NP-hard when for any problem ''L'' in NP, there is a polynomial-time reduction from ''L'' to ''H''〔 An equivalent definition is to require that any problem ''L'' in NP can be solved in polynomial time by an oracle machine with an oracle for ''H''. Informally, we can think of an algorithm that can call such an oracle machine as a subroutine for solving ''H'', and solves ''L'' in polynomial time, if the subroutine call takes only one step to compute. Another definition is to require that there is a polynomial-time reduction from an NP-complete problem ''G'' to ''H''.〔 As any problem ''L'' in NP reduces in polynomial time to ''G'', ''L'' reduces in turn to ''H'' in polynomial time so this new definition implies the previous one. It does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NP-hardness」の詳細全文を読む スポンサード リンク
|