0
$\begingroup$

I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.

$\endgroup$
4
$\begingroup$

According to the space hierarchy theorem, there is a language in $\mathrm{SPACE}(n^{556})$ which is not in $\mathsf{SPACE}(n^{555})$. A padded version of this language will be in $\mathsf{SPACE}(n^{555})$. If the latter is equal to $\mathsf{NP}$, then the original language would also be in $\mathsf{NP} = \mathsf{SPACE}(n^{555})$, since we can implement padding while remaining inside $\mathsf{NP}$.

I'll let you flesh out this argument.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.