8
$\begingroup$

Can we say that there are some problems that take exponential time even if $P=NP$

For instance problems like: enumerating all spanning trees of a graph, enumerating all hamiltonian paths of a graph, listing all permutations of string.

  • 0
    I like this question. I already figured out that there are problems that require near exponential time to compute and can be computed in exponential time. If it can also be proven that all problems that can be computed in exponential time can also be computed in polynomial time assuming P = NP, that would disprove P = NP.2018-10-24

2 Answers 2

8

Yes, the time hierarchy theorem tells us that $P \subsetneq EXP$.

Take for example the following language: $\{ \langle M,x,1^n \rangle \mid \textrm{M accepts x in } 2^n \textrm{ time}\}.$ This language is obviously complete for $EXP$ and thus cannot be contained within $P$.

  • 0
    P = NP hasn't been proven so just because it's provable that there are exponential time problems if$P$= NP doesn't mean it's not also provable that there are no exponential time problems if$P$= NP. The author probably meant you to look for a way to prove that if P = NP, then there are no exponential time problems because from that, P = NP could easily be disproven.2018-07-12
6

Yes.

First, at least for your last example this is obvious because there are n! many permutations of a string of length n. So listing all these, gives exponentially long output and this will take exponential time.

Secondly, note that these problems do not belong to the same class of complexity classes as P or NP since they make an output, while P and NP are decision problems. I do not know the answer for the corresponding decision problems of your examples. However, the answer is still yes by the time hierarchy theorem implies that there are problems that take exponential time.