3
$\begingroup$

Assuming $P \ne NP$, is there a problem such that is NP such that:

  • There is always a solution
  • On average, it takes exponential time to solve
  • The probability distribution can be any distribution which can be sampled from in polynomial time.

Also, what would such a complexity class be called?

$\endgroup$
4
  • 2
    $\begingroup$ It is consistent with P$\neq$NP that all problems in NP can be solved in subexponential time. $\endgroup$ May 10, 2016 at 7:33
  • $\begingroup$ Does "given from an entropy source" correspond to "there exists an entropy source" or "for all entropy sources"? ​ If the latter, does that quantifier come before of after "there exists an algorithm"? ​ ​ ​ ​ $\endgroup$
    – user12859
    May 10, 2016 at 10:50
  • $\begingroup$ Random $k$-SAT with an appropriate clause density fits the bill. $\endgroup$ May 10, 2016 at 13:56
  • $\begingroup$ @RickyDemer I was thinking the ability to flip fair coins. $\endgroup$ May 10, 2016 at 18:52

2 Answers 2

1
$\begingroup$

We don't know. It's possible that $P \ne NP$ but still all problems can be solved in subexponential time, as Yuval states. The Exponential Time Hypothesis is a conjecture that a certain problem requires exponential time to solve, but it's a conjecture -- there's debate among researchers about whether we should expect it to hold or not.

Assuming the ETH, you can find problems that meet your requirements, at least for worst-case hardness: there is asymptotically almost surely a solution, and any deterministic algorithm must have worst-case running time that's exponential in the length of the input. In particular, ETH implies that every problem in the class SNP takes exponential time to solve. For instance, 3SAT would qualify.

It sounds like you really want average-case hardness. There are some natural candidate problems: 3SAT with an appropriate clause density would be one reasonable one.

You could also use cryptographic hardness assumptions from the crypto community, e.g., inverting $f(k) = AES_k(0)$ probably takes exponential time yet is known to have a solution, as far as we can tell given our current state of knowledge. This gives you a problem with a concrete parameter size, but with standard techniques you can build something asymptotic if you prefer an asymptotic family of problems.

$\endgroup$
0
$\begingroup$

I'm not big on complexity classes and their definitions so this answer might not be correct. My suggestion is too long to fit in a comment, though.

Your description made me think about PPAD(-complete (?)) introduced by Papadimitriou.

The, as far as I'm aware, most associated problem with PPAD-complete is computing a mixed Nash equilibrium (NE) in two player games. Such NE is not efficiently computable and a problem instance can be generated in polynomial time.

$\endgroup$
2
  • $\begingroup$ Why do you think these problems take exponential time to solve? I don't think there's any known result that PPAD-complete problems take exponential time to solve; as far as I know, it's possible they can all be solved in subexponential time (even if P != NP, etc.). $\endgroup$
    – D.W.
    May 10, 2016 at 17:04
  • $\begingroup$ @D.W. I don't know. Sorry. $\endgroup$
    – Auberon
    May 10, 2016 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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