# Set of Turing machines that accepts at least one input in bounded time

What is known about the languages:

$$S_f = \{ [M] \ | \ \exists{x} \ \text{s.t.} \\ M \ \text{accepts} \ x \ \text{in} \ f(|[M]|) \ \text{steps}, \\ \ |x| \leq f(|[M]|) \}$$

I used to think that in order to check whether a string $$[M]$$ is in $$S_f$$ you cannot avoid simulating $$M$$ on all possible $$x$$ whose length is less than $$f(|[M]|)$$.
But for a polynomial $$f$$, verifying a candidate solution $$x$$ takes polynomial time so that $$S_f \in NP$$, while trying all of them is exponential, which would prove $$P \neq NP$$ ...

So my reasoning is spectacularly wrong, but I can't find out why:

1. Maybe $$S_f$$ is in fact not in $$NP$$ when $$f$$ is polynomial?
2. Maybe it is possible to check whether a string $$[M]$$ is in $$S_f$$ without trying most of the possible $$x$$?
3. Something else?
• Can you identify a more specific question? "What is known about...?" sounds overly broad. Also we expect that you ask one question per post, not two or three. I'm not sure what "appartenance" means -- that might have been a translation failure.
– D.W.
Sep 12, 2022 at 20:58
• Thanks, indeed it was a huge translation failure. There is a single question: "Why is my reasoning wrong" Sep 13, 2022 at 5:21

Your reasoning is wrong because you assert something without proof. You just assert that the only way to do it is to try all $$x$$, but there is no justification given for this assertion, and we don't know whether that assertion is true. Just because you can only think of one way to solve a problem, doesn't mean it is the only way. There could be another way that you haven't thought of yet. As you indicate, given the relationship to the P vs NP question, your assertion amounts to assuming something that we don't have a proof of. It'd be like saying "Well, P is different from NP, because the only way to solve a NP-complete problem is to try all possible solutions". We have no proof of such a claim (and indeed, such a claim is unlikely to be true).