# Is the following statement a correct formulation of the (much doubted) P = NP conjecture?

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

-
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 –  Gerhard Paseman Mar 14 '11 at 20:10
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. –  Michael Beeson Mar 14 '11 at 22:45

## 1 Answer

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.
-
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. –  Theo Johnson-Freyd Mar 14 '11 at 23:51
@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. –  John Bentin Mar 15 '11 at 9:38