The class NP is the set of decision problems for which
Aa proposed answer (certificate) can be verified in polynomial time
Ban answer can be found in polynomial time on any input
Cno polynomial-time algorithm can ever exist
Dthe input size is at most polynomial in the answer
Answer & Solution
Correct answer: A. a proposed answer (certificate) can be verified in polynomial time
NP problems have polynomial-time verifiers, not necessarily polynomial-time solvers. Given a candidate solution (certificate), you can check it quickly. Finding the certificate may still be exponential. The other options describe P (option B), undecidable problems (option C), or unrelated input/answer size relationships.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?Floyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is