For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string 𝑝 in the enumeration, does there exist some other string (certificate) 𝑐 that allows you to verify 𝑝 is a member of the enumeration in poly time? I believe that it might be possible in poly time because all we have to do is check if a string fits some certain format (format of the encoding)?

A decision problem $P$ is poly time verifiable iff there is an algorithm 𝑉 called verifier such that if $P(w)=$π‘ŒπΈπ‘† then there is a string $c$ s.t. $𝑉(w,c)=$π‘ŒπΈπ‘†, if $P(w)=𝑁𝑂$ then for all strings $c$, $𝑉(w,c)=$𝑁𝑂 and V runs in $O(w^{k})$ for some constant $k$ for all inputs $w$.


I think you can force the enumeration to be only on machines with a very strict format: a hard-coded poly time "clock" at the start, and after that the rest of the TM.

This will allow you to check in poly time (not even requiring a verifier) whether a given string $p$ is a part of the enumeration

  • $\begingroup$ So, this means that some languages representing P (encoding all languages in P) are in P. cool. I want to accept but how can i know if this is true? seems reasonable! $\endgroup$ – DeeDee Jun 21 '20 at 22:49
  • 1
    $\begingroup$ In fact, I think this reasoning should work for any deterministic complexity class you want to enumerate on, and the algorithm that checks whether the string is a part of the enumeration will still be poly time $\endgroup$ – nir shahar Jun 21 '20 at 22:53
  • $\begingroup$ what is the reasoning (you are saying specify larger and larger clocks at the start for each larger complexity class)? i believe the main problem is only poly time verifiable not poly time solvable because, if it were, i think you can derive a contradiction. $\endgroup$ – DeeDee Jun 21 '20 at 23:00
  • 1
    $\begingroup$ For a specific enumeration we define it can be done in the exact same way: add a counter to the start of every turing machine $\endgroup$ – nir shahar Jun 21 '20 at 23:01
  • $\begingroup$ Do you think you can you efficiently simulate the machines in the enumeration on any input? $\endgroup$ – DeeDee Jun 21 '20 at 23:23

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.