Activity $4$: Consider the verification definition of $NP,$ paying close attention to the requirement on

the length of the certificate. We can state this more formally, as in lecture, as:

The complexity class $NP($as a verification problem$)$:

LinNP iff there exists a deterministic$(!)TMV$ where:

winL iff EEc, $inL(V{)}^{{?}^{?}}$len$(c)f(|w|)$ for some finO$(n^k)$

timereq$($V$)O(n^k)$ for some constant $k($implies $V$ always halts$)$

This was the definition we proved equivalent to the deciding NDTM characterization of $NP$

$($recalled above$).$ Explain why the polynomial bound on the size of the certificate $($that the size of

the certificate is bounded by some polynomial function of the length of the input$)$ is important to

that equivalence. In particular, consider what goes wrong if you try to prove the equivalence of the

${?}^1$ Technically there are two flavors of ILP, one given as an optimization problem where there is an additional

expression whose value should be maximized or minimized, and the decision problem version above.

deciding NDTM description of $NP($definition $1$ at the top of the page$)$ and the following incorrect

variant of the verifier characterization where there is no limit on the size of the certificate, as in:

The complexity class $($as a verification problem$)$:

Lin$$ iff there exists a deterministic$(!)$ TM $V$ where:

winL iff EEc, $inL(V)$

timereq$(V$ for some constant $k($implies $V$ always halts$)$

The only difference between this definition and the correct verifier definition is that we removed

the limit on the size of the certificate.

Every language $L$ in $NP$ by the NDTM definition is also in $$ as just defined $($the same build$-$a$-$

verifier$-$from$-$a$-$nondeterministic$-$decider approach works just fine for this$).$ But what goes wrong

in try to show that every language in $$ is in the deciding characterization of $NP?$

For this activity you are not permitted to simply say that the NDTM characterization of $NP$ is

equivalent to the verifier version, and the verifier version requires the extra size restriction. What

goes wrong if you try to directly construct a decider from a verifier with no limit on certificate size?