Question

What is the definition of an NP-hard problem?

A A problem that can be solved in polynomial time on non-deterministic Turing machines. Correct Answer Incorrect Answer
B A problem that is solvable in polynomial time on deterministic Turing machines. Correct Answer Incorrect Answer
C A problem that is at least as hard as the hardest problems in NP. Correct Answer Incorrect Answer
D A problem that is solvable using dynamic programming techniques. Correct Answer Incorrect Answer
E None of these Correct Answer Incorrect Answer

Solution

A problem that is at least as hard as the hardest problems in NP.

Practice Next

Relevant for Exams:

×
×