# NP problems with exponentially complex average time solution?

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?

• It is consistent with P$\neq$NP that all problems in NP can be solved in subexponential time. May 10, 2016 at 7:33
• 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"? ​ ​ ​ ​
– user12859
May 10, 2016 at 10:50
• Random $k$-SAT with an appropriate clause density fits the bill. May 10, 2016 at 13:56
• @RickyDemer I was thinking the ability to flip fair coins. May 10, 2016 at 18:52

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.

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.