Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  sdcvvc Dec 3 '11 at 16:49
    
This question would have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! –  Raphael Dec 3 '11 at 17:30
    
@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. –  sxd Dec 3 '11 at 17:38

2 Answers 2

up vote 7 down vote accepted

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$.

share|improve this answer
    
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?? –  rakesh Nov 29 '11 at 8:50
    
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$. –  sxd Nov 29 '11 at 12:18
    
thankyou.. dimitri –  rakesh Nov 29 '11 at 17:39
    
@rakesh, no problem! –  sxd Nov 29 '11 at 18:45

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.

share|improve this answer
    
thankyou... claudi –  rakesh Nov 29 '11 at 17:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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