# 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

• @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