Wikipedia gives a proof sketch of the time hierarchy theorem by showing that appartenance to the following language:
$$H_f = \{([M], x) \ | \ M \ \text{accepts} \ x \ \text{in} \ f(|x|) \ \text{steps}\}$$
cannot be checked faster than by actually running $M$ on $x$ for $f(|x|)$ steps.
It makes me wonder what is known about the language:
$$S_f = \{ [M] \ | \ \exists{x} \ \text{s.t.} \\ M \ \text{accepts} \ x \ \text{in} \ f(|[M]|) \ \text{steps}, \\ \ |x| < f(|[M]|) \}$$
To me it looks like that for a given $M$ you have no other solution than to try all possible $x$ smaller than $f(|[M]|)$.
For $f$ polynomial, verifying a candidate solution $x$ is polynomial, but trying them all is exponential, which would prove $P \neq NP$ ...
So my reasoning is obviously wrong but I can't figure out why, and I also wonder more generally what is known about $S_f$ ?
The main problem is that this proposal does not block a "clever" solution. So maybe the whole P versus NP problem can be solved in polynomial time with some clever trick. Maybe there's an NP-Complete sparse language out there somewhere to which all NP-complete problems can be reduced. Or maybe something that feels like a natural proof that gets around the barriers. Or some beautiful number theory or algebraic trick.
More generally, maybe the structure of NP-complete problems is simpler than we currently understand. So a correct proof that P does not equal NP would have to block all these tricks, potentially infinitely many of them.
This list might also be helpful if you haven't seen it already.