-1
$\begingroup$

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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jun 21, 2020 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
    Commented Jun 21, 2020 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
    Commented Jun 21, 2020 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
    Commented Jun 21, 2020 at 23:01
  • $\begingroup$ Do you think you can you efficiently simulate the machines in the enumeration on any input? $\endgroup$
    – DeeDee
    Commented Jun 21, 2020 at 23:23

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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