"Call a Turing machine $A$ a d-machine if, for some polynomial $p(\cdot)$, when $A$ starts with any input string, say of length $n$, in its alphabet on its (otherwise blank) tape, it will halt in a number of steps bounded by $p(n)$ with its tape either blank or bearing just a string of length $n$. Then each d-machine $A$ corresponds to a d-machine $B$ which, when started with any input string in its alphabet, will halt with a blank tape, if $A$ halts with a blank tape for every input the length of $B$'s input, and otherwise will halt with an output tape that, input to $A$, will lead to $A$ halting with a non-blank tape."

Interpretation: Input for $A$ codes candidate "solutions" while blank/non-blank output indicates just refutation/verification. For $B$, input marks only length while output codes an $A$-verifiable solution.

  • $\begingroup$ I suspect not. If you can say something about the correspondence, e.g. it is polynomial in time or space with respect to some parameters involving A and or B, then maybe. Otherwise your formulation might be equivalent to "There is an oracle O such that P^O = NP^O." I've been wrong before though. Gerhard "Has Sometimes Been Wrong Before" Paseman, 2011.03.14 $\endgroup$ – Gerhard Paseman Mar 14 '11 at 20:10
  • $\begingroup$ I think you should edit the last line to say "containing a string the same length as B's input, that, input to A, will lead to A halting with a non-blank tape. $\endgroup$ – Michael Beeson Mar 14 '11 at 22:45

This is a correct formulation of P=NP, with two caveats:

  • The blank character cannot be considered part of the alphabet. Otherwise a length n+1 string with a blank at the end is indistinguishable to a length n string.
  • P=NP is usually defined as "If it possible to recognize a solution it is possible to find out if there is a solution". You define it as "If it is possible to recognize a solution it is possible to find a solution". However, these to formulations are equivalent.
  • $\begingroup$ Just a follow-up, in case anyone is surprised (as I was) that "find if there is a solution" is equivalent to "find a solution". Basically, the idea is: If you have a machine that decides quickly if a solution exists, then the guess-and-check method runs quickly. $\endgroup$ – Theo Johnson-Freyd Mar 14 '11 at 23:51
  • $\begingroup$ @itaibn: Thanks for your answer. I don't think that the absence of a character (i.e. blank) is a sort of character (i.e. an element of the alphabet), but perhaps some people do; so your first point is worth making. In this input--output formulation, machine $A$ needs a defined solution to work on. Thank you, and Theo, for pointing out the polynomial-time equivalence of detecting and identifying a solution. $\endgroup$ – John Bentin Mar 15 '11 at 9:38

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.