In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex format. can we use $a^n b^n c^n d^n$ format for our guesses?

  • 1
    $\begingroup$ The language consisting of all strings of the form $a^nb^nc^nd^n$ isn’t regular! $\endgroup$ – Yuval Filmus Jul 28 '18 at 16:12

You cannot force the guesses in any way.

That said, in your case you can emulate a witness of this form. Let’s first replace your $n$ with $m$, reserving $n$ for the input length. Suppose that your algorithm runs in time $t(n)$. Then you can only go through the first $t(n)$ guesses, so without loss of generality you can assume that $m \leq t(n)$. Since $t(n)$ is polynomial, $\log t(n) = O(\log n)$, and so you have enough space on the tape to store $m$. You therefore proceed as follows:

  • Guess $m$ (by guessing $\log t(n)$ bits).
  • Simulate the guesses $a^mb^mc^md^m$ using a counter that goes up to $m$ and another one that goes up to 4.

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.