0
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 12 at 20:58
  • $\begingroup$ Thanks, indeed it was a huge translation failure. There is a single question: "Why is my reasoning wrong" $\endgroup$
    – agemO
    Sep 13 at 5:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So 1. is true but we don't know about 2. ? $\endgroup$
    – agemO
    Sep 13 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.