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
    You mentioned problems which must take exponential time in worst case, since they have to output an exponentially long string. The $P=NP$ question is about decision problems, where the output is either 0 or 1, so this bound does not apply.2011-12-03
  • 0
    This question would have been perfect for the upcoming [Computer Science Stack Exchange](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2). So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off!2011-12-03
  • 0
    @rakesh, it is always nice that you accept the answer you find most desirable, this because: 1 it is nice to the people who answered and 2, else the question remains under the unanswered section of the website.2011-12-03
  • 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

7

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
    How can we say that: $$L=\{ \langle M,x,1^n \rangle \mid \textrm{M accepts x in } 2^n \textrm{ time}\}.$$ is not in P, for instance if M' accepts L, M' on input $\langle M,x,1^n \rangle$, instead of "directly simulating M on x and seeing if M accepts x in $2^n$ time", M'could somehow be clever and decide if "M accepts x in $2^n$ time" in polynomial time??2011-11-29
  • 0
    Since $P \subsetneq EXP$, we know that any complete language for $EXP$ cannot be in $P$, else $P = EXP$. Therefore, since $L$ is $EXP$-complete it cannot be in $P$.2011-11-29
  • 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.