0
$\begingroup$

There's a standard trick I've heard about in reductions where you just halt a machine and reject after some polynomial amount of time if it hasn't accepted yet. Can this be applied to nondeterministic Turning machines, and if not then why?

For example, suppose we had a nondeterministic Turing machine $M$ for SAT. Given a formula $\phi$, let $M$ guess an assignment to $\phi$ if it's satisfiable, and otherwise let it start exhaustively checking that no assignment satisfies $\phi$. Halt $M$ and reject after some length of time that's polynomial in $|\phi|$ if it hasn't accepted by then. Which would of course imply that SAT is in coNP, which it probably isn't.

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.