0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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
    Commented Mar 14, 2011 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
    Commented Mar 14, 2011 at 22:45

1 Answer 1

Reset to default
3
$\begingroup$

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.
Improve this answer
$\endgroup$
2
  • $\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
    Commented Mar 14, 2011 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
    Commented Mar 15, 2011 at 9:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .