NP is a class of decision problems for which one can present a "certificate" that can be verified in polynomial time.

Are there any decision problems that have such "certificates" that can be verified faster than solving the problem(*), but verifying still takes superpolynomial time(*)?

(*) using the best-known method


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.