NP-hard

NP-hard

Dictionary

Tutorials

Encyclopedia

Dictionary

Directory

Dictionary results for: NP-hard

Email this to a friend NP-hard

NP-hard

Source: The Free On-line Dictionary of Computing (27 SEP 03)
NP-hard

	NP-hard
     
         A set or property of computational search
        problems.  A problem is NP-hard if solving it in polynomial
        time would make it possible to solve all problems in class
        NP in polynomial time.
     
        Some NP-hard problems are also in NP (these are called
        "NP-complete"), some are not.  If you could reduce an NP
        problem to an NP-hard problem and then solve it in polynomial
        time, you could solve all NP problems.
     
        See also computational complexity.
     
        [Examples?]
     
        (1995-04-10)