Matches in DBpedia 2014 for { <http://dbpedia.org/resource/NP-hard> ?p ?o. }
Showing items 1 to 44 of
44
with 100 items per page.
- NP-hard abstract "NP-hard (Non-deterministic Polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., L ≤ TH). In other words, L 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. NP-hard problems may be of any type: decision problems, search problems, or optimization problems.As consequences of the definition, the following claims can be made: Problem H is at least as hard as L, because H can be used to solve L; Since L is NP-complete, and hence the hardest in class NP, also problem H is at least as hard as NP, but H does not have to be in NP and hence does not have to be a decision problem (even if it is a decision problem, it need not be in NP); Since NP-complete problems transform to each other by polynomial-time many-one reduction (also called polynomial transformation), all NP-complete problems can be solved in polynomial time by a reduction to H, thus all problems in NP reduce to H; note, however, that this involves combining two different transformations: from NP-complete decision problems to NP-complete problem L by polynomial transformation, and from L to H by polynomial Turing reduction; If there is a polynomial algorithm for any NP-hard problem, then there are polynomial algorithms for all problems in NP, and hence P = NP; If P ≠ NP, then NP-hard problems cannot be solved in polynomial time, while P = NP does not resolve whether the NP-hard problems can be solved in polynomial time; If an optimization problem H has an NP-complete decision version L, then H is NP-hard.A common mistake is to think 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.".
- NP-hard thumbnail P_np_np-complete_np-hard.svg?width=300.
- NP-hard wikiPageID "54681".
- NP-hard wikiPageRevisionID "590492489".
- NP-hard hasPhotoCollection NP-hard.
- NP-hard subject Category:Complexity_classes.
- NP-hard subject Category:NP-hard_problems.
- NP-hard type Abstraction100002137.
- NP-hard type Attribute100024264.
- NP-hard type Class107997703.
- NP-hard type Collection107951464.
- NP-hard type ComplexityClasses.
- NP-hard type Condition113920835.
- NP-hard type Difficulty114408086.
- NP-hard type Group100031264.
- NP-hard type NP-hardProblems.
- NP-hard type Problem114410605.
- NP-hard type State100024720.
- NP-hard comment "NP-hard (Non-deterministic Polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., L ≤ TH). In other words, L can be solved in polynomial time by an oracle machine with an oracle for H.".
- NP-hard label "NP-Schwere".
- NP-hard label "NP-difficile".
- NP-hard label "NP-difícil".
- NP-hard label "NP-hard".
- NP-hard label "NP-hard".
- NP-hard label "NP-moeilijk".
- NP-hard label "NP困难".
- NP-hard label "NP困難".
- NP-hard label "Problem NP-trudny".
- NP-hard label "مسائل NP صعبة".
- NP-hard sameAs NP-Schwere.
- NP-hard sameAs NP-hard.
- NP-hard sameAs NP-difficile.
- NP-hard sameAs NP困難.
- NP-hard sameAs NP-난해.
- NP-hard sameAs NP-moeilijk.
- NP-hard sameAs Problem_NP-trudny.
- NP-hard sameAs NP-difícil.
- NP-hard sameAs m.0f86q.
- NP-hard sameAs Q1137554.
- NP-hard sameAs Q1137554.
- NP-hard sameAs NP-hard.
- NP-hard wasDerivedFrom NP-hard?oldid=590492489.
- NP-hard depiction P_np_np-complete_np-hard.svg.
- NP-hard isPrimaryTopicOf NP-hard.
