Question

Which statement accurately describes an NP-complete problem?

A An NP-complete problem is any problem that can be solved in polynomial time. Correct Answer Incorrect Answer
B An NP-complete problem is a problem that is both in NP and NP-hard. Correct Answer Incorrect Answer
C An NP-complete problem can only be solved using exponential time algorithms. Correct Answer Incorrect Answer
D An NP-complete problem is a problem that can be verified in logarithmic time. Correct Answer Incorrect Answer
E None of these Correct Answer Incorrect Answer

Solution

An NP-complete problem is a problem that is both in NP and NP-hard.

Practice Next

Relevant for Exams:

×
×