Question

Give brief answers (of one or two sentences) to the following questions.

(a) What does it mean for a decider to be efficient?
(b) What must be shown to prove that a language L∈P?
(c) What does it mean for a verifier to be efficient?
(d) What criteria must an algorithm V satisfy to be an efficient verifier for a language L?
(e) What must be shown to prove that a language L∈NP?

Answer 1

Efficiency of deciders and verifiers in computational complexity theory.

Step-by-step explanation:

(a) For a decider to be efficient, it means that it can determine whether an input belongs to a language or not in a reasonable amount of time.
(b) To prove that a language L∈P, it must be shown that there exists a polynomial-time algorithm that decides L.
(c) For a verifier to be efficient, it means that it can verify the correctness of a solution to a problem in a reasonable amount of time.
(d) An algorithm V must satisfy the criteria of being polynomial-time and have the property of accepting only valid solutions to a problem in order to be an efficient verifier for a language L.
(e) To prove that a language L∈NP, it must be shown that there exists a polynomial-time verifier for L.