3
$\begingroup$

It is proven by Time hierarchy theorem that EXPTIME-complete do not belong to P even if we do not know if NP belong to P.

Before I read wiki, I found EXPTIME algorithm for solving 3-sat, the brute algorithm $O(2^n)$. Could I announced then, that there could not be polynomial solution for 3-sat?

  1. Time hierarchy theorem prove that there are EXPTIME problems that are not in P. But how can you prove that problem is EXPTIME and not super-polynomial time?

  2. Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

*If you have solution for just one of the questions it's fine.

$\endgroup$
  • 6
    $\begingroup$ "Could I announced then, that there could not be polynomial solution for 3-sat?" No. Just because you know a slow way to do something doesn't mean there isn't a fast way to do that thing. $\endgroup$ – G. Bach Dec 8 '13 at 16:11
9
$\begingroup$

No, that doesn't prove there's no polynomial time solution for 3-SAT, for a couple of reasons.

  1. Saying that you have an $O(2^n)$ algorithm for something only provides an upper bound. The algorithm takes no more than some constant times $2^n$ steps, for big enough $n$ but I can tell you that I have no more than one trillion dollars in the bank and you still have no idea how wealthy I am.

  2. If your suggested argument was solid, the following would be a direct proof that $\mathrm{P}\neq\mathrm{EXP}$. Here's an exponential-time, brute-force recursive algorithm for graph connectivity: check that every proper subset of the graph's vertices is connected and sends an edge to at least one vertex not in the subset. This can't prove that there's no polynomial time algorithm for graph connectivity because we already know that plenty of those exist. Similarly, observing that you have an exponential-time algorithm for 3-SAT doesn't prove that there isn't also a polynoial one.

  3. $\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{EXP}$ so we already know there is an exponential-time algorithm for every problem in $\mathrm{P}$ and $\mathrm{NP}$. Knowing that 3-SAT is in $\mathrm{EXP}$ tells you nothing new. However, if you could prove that 3-SAT is $\mathrm{EXP}$-complete, that would prove that $\mathrm{NP}=\mathrm{EXP}$ and, since we know that $\mathrm{P}\neq\mathrm{EXP}$ from the time hierarchy theorem, that would prove $\mathrm{P}\neq\mathrm{NP}$. But it's very unlikely that 3-SAT is $\mathrm{EXP}$-complete. :-)

[...] how can you prove that problem is EXPTIME and not super-polynomial time?

"Super-polynomial" just means "more than a polynomial". EXPTIME is an example of a super-polynomial time complexity class.

Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

That doesn't make sense. A polynomial is a polynomial so it can be expressed as a polynomial; a function that's super-polynomial isn't a polynomial so it can't be expressed as a polynomial. I'm not sure why you've latched onto this phrase "polynomial expression".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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