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