# Deciding whether a turning machine guaranteed to halt solves sat [closed]

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?

• 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. Jan 8 '14 at 21:32
• 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. Jan 8 '14 at 22:35
• 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
– relG
Jan 8 '14 at 22:44
• 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. Jan 8 '14 at 22:51
• 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
– relG
Jan 8 '14 at 23:14

## 1 Answer

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.

• I think the assertion "this is... no harder than the property you describe" requires proof. Jan 8 '14 at 21:34
• 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.) Jan 8 '14 at 21:50
• 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.
– relG
Jan 8 '14 at 21:58
• @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.") Jan 8 '14 at 22:19
• @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?
– relG
Jan 9 '14 at 17:15