CSC 341 (Fall 2021)

Lab: NP-Completeness

Problem 1: Bridging the Gap

Let \(A\) be a decidable language and \(V\) be a polynomial-time verifier for the language. Recall that a verifier is an algorithm that checks whether a candidate solution to the problem is indeed an actual solution. Give a generic non-deterministic Turing machine \(N\) that decides \(A\) in polynomial time in terms of \(V\).

Problem 2: Membership

Show that each of the following languages are in \(\mathsf{NP}\).

Problem 3: Completeness

Define the following languages:

Show that \(\mathsf{CLIQUE} \leq_p \mathsf{ISO}\).

(Hint: what is the type of the mapping function \(f\) in this case?)