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

Question

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?

Answer 1

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

You might also be interested in the strong exponential time hypothesis. That too is unproven, but it represents a more precise formalization of a conjecture that might well be true, and is closely connected to the topic you are asking about.