<p>Suppose I give as input a Turing machine M <em>guaranteed to halt in time n^c</em> 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?</p>

<p>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?</p>

CC BY-SA 3.0
2014-01-08T21:32:02.253Z
This is not a research-level question so is [off-topic, here](http://cstheory.stackexchange.com/help/on-topic).  Since it's been answered, it should probably be migrated to [Computer Science Stack Exchange](http://cs.stackexchange.com).
David Richerby
CC BY-SA 3.0
2014-01-08T22:35:34.670Z
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.
David Richerby
CC BY-SA 3.0
2014-01-08T22:44:16.383Z
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
CC BY-SA 3.0
2014-01-08T22:51:28.187Z
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.
David Richerby
CC BY-SA 3.0
2014-01-08T23:14:27.860Z
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
CC BY-SA 3.0
2014-01-08T23:17:57.343Z
btw- I think M and M' got mixed up in your last 2 sentences
relG
CC BY-SA 3.0
2014-01-14T19:27:27.467Z
I would like all the people who said my question is not research level to see if they can actually find a solution. The promise makes it very non-trivial. It is not something that Rice's thm can handle. We learn in undergrad that computability is pretty much understood, and that is maybe why people taking a shallow glance at my question think it is an undergrad exercise. But it seems we do not know much when we are not allowed to rely on the halting problem - as my promise on the input requires
relG
<np><decidability>
Deciding whether a turning machine guaranteed to halt solves sat
relG
# Deciding whether a turning machine guaranteed to halt solves sat

(Asked by: username_0 on 2014-01-08)

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?

**Tags:** np, decidability

> **Comments:**
> **username_1**: This is not a research-level question so is [off-topic, here](http://cstheory.stackexchange.com/help/on-topic).  Since it's been answered, it should probably be migrated to [Computer Science Stack Exchange](http://cs.stackexchange.com).  
> **username_1**: 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.  
> **username_0**: 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  
> **username_1**: 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.  
> **username_0**: 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  
> **username_0**: btw- I think M and M' got mixed up in your last 2 sentences  
> **username_0**: I would like all the people who said my question is not research level to see if they can actually find a solution. The promise makes it very non-trivial. It is not something that Rice's thm can handle. We learn in undergrad that computability is pretty much understood, and that is maybe why people taking a shallow glance at my question think it is an undergrad exercise. But it seems we do not know much when we are not allowed to rely on the halting problem - as my promise on the input requires  

---

## 0 answers

