Suppose I give as input a Turing machine M guaranteed to halt in time n^c on inputs of length n for a universal constant c. Is there a Turing machine that given any such M can decide whether M solves SAT?

Remarks: - could it be that there is an N depending on c and the description size of M such that if M doesn't solve SAT it answers wrong on an input of length at most N?


closed as off-topic by Marzio De Biasi, Sasho Nikolov, Hsien-Chih Chang 張顯之, András Salamon, Artem Kaznatcheev Jan 12 '14 at 12:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Marzio De Biasi, Sasho Nikolov, Hsien-Chih Chang 張顯之, András Salamon, Artem Kaznatcheev
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ This is not a research-level question so is off-topic, here. Since it's been answered, it should probably be migrated to Computer Science Stack Exchange. $\endgroup$ – David Richerby Jan 8 '14 at 21:32
  • $\begingroup$ I don't mean to discourage you but I don't think my comment is at all unfair. Once the fine details are sorted out, it seems likely that Philip White's answer will be correct: if P=NP, the problem is certainly trivial; otherwise, undecidability should follow quickly from Rice's Theorem and, thus, require only an undergraduate level of knowledge. Two people disagreeing on whether the first answer is 100% correct does not make it a research question. $\endgroup$ – David Richerby Jan 8 '14 at 22:35
  • $\begingroup$ Like I said the n^c was rather arbitrary and can be switch,e.g. to 2^n - in which case P!= NP doesn't make the language empty.. the point is more about whether the promise about halting makes it decidable. I think it's quite an interesting research direction: given a potential `witness' that P=NP - an algorithm that supposedly solves SAT, can we check whether it is correct $\endgroup$ – relG Jan 8 '14 at 22:44
  • 3
    $\begingroup$ The running time restriction doesn't seem to make any crucial difference. Given a TM $M$, let $M'$ be the machine that simulates $M$ for $n^c$ (or $2^n$ or whatever) steps and rejects if $M$ has not yet halted. Deciding whether $M$ solves SAT with the promise is the same as deciding whether $M'$ solves SAT without the promise. Whether $M'$ solves SAT is undecidable by Rice's theorem. $\endgroup$ – David Richerby Jan 8 '14 at 22:51
  • 1
    $\begingroup$ If I understand correctly Rice's thm implies it is undecidable whether given a TM M , it solves SAT. You want to say it also undecidable whether given a TM M (that maybe doesn't always halt) it solves SAT with in n^c (or some other f(n) ) steps. I don't see why the first statement implies the second $\endgroup$ – relG Jan 8 '14 at 23:14

Assuming P != NP, the answer is surely yes; based on your guarantee, you've restricted the problem to polynomial time machines, and thus the language you describe should be trivially empty. The challenge is proving that a machine that rejects every input truly decides the language--not just finding this machine.

Of course, if P = NP, you have a Rice's theorem problem (and the answer is no). Since the language is now non-trivial, you're describing a non-trivial property of some Turing machines--specifically, the ones bounded by n^c.

The following is drawn from David Richerby's comment above. Given a Turing machine M1, let M2 be a machine that simulates M1 and rejects if it hasn't halted after n^c steps. Deciding whether a machine M1 solves SAT with the promise (that the machine halts after n^c steps) is equivalent to deciding whether M2 solves SAT without the promise. Deciding M2 without the promise is undecidable, by Rice's theorem.

  • $\begingroup$ I think the assertion "this is... no harder than the property you describe" requires proof. $\endgroup$ – David Richerby Jan 8 '14 at 21:34
  • $\begingroup$ You mean, proving that: "being a TM that is bounded by n^c and that decides SAT" is no harder than the property he describes...requires proof? His property is: "being a TM that decides SAT, with only TMs that run in time n^c considered." To see that these are equally hard, we can just consider the latter property, but with other TMs considered (that do not run in n^c). All of these other TMs are "no" instances; now the properties are exactly the same. (Or did you mean something else? Also, I have no problem with migrating this to CS.SE.) $\endgroup$ – Philip White Jan 8 '14 at 21:50
  • $\begingroup$ Can Rice's theorem apply to promise problems? I am not requiring the machine to answer in a certain way, or even halt, on inputs that are not in the promise - i.e., TMs that do not halt in time n^c on some input. btw the n^c was a bit arbitrary.. the point was just to avoid "halting issues" causing undecidability. If you can answer the question with "M guaranteed to halt in time n^c on inputs of length n for a universal constant c" switched by "M guaranteed to halt on every input of length n in time f(n) for some function f" I would also find that interesting. $\endgroup$ – relG Jan 8 '14 at 21:58
  • $\begingroup$ @PhilipWhite Yes, that's what I mean needs proof. The fact that all the instances you're adding are 'no' instances doesn't make it trivial, as you're suggesting, because, when presented with an input, you have to determine whether a given instance is one of the original ones or one of the trivial new 'no' instances. (To put it another way, if your argument worked, the zero-input halting problem would be decidable: "Consider the class of TMs that halt on input zero. For this class, the problem is trivial. All other instances are 'no' instances, so the problem without the promise is no harder.") $\endgroup$ – David Richerby Jan 8 '14 at 22:19
  • 1
    $\begingroup$ @PhilipWhite - thanks for your edited response. But I think it is incorrect. You write `Deciding wheter M1 solves SAT with the promise..' but this doesn't make complete sense- given the promise we don't have to decide anything or even halt on M1 if it doesn't always halt after n^c steps. If you could use M2 to decide if M1 solves SAT (not necessarily in time n^c) I would be convinced of undecidability. David Richerby - opinions? $\endgroup$ – relG Jan 9 '14 at 17:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.