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.

Consider a reduction of an NP-complete problem to a polynomial-time problem. What will be the consequence, if any, if • the reduction takes polynomial time? • the reduction takes exponential time?

share|improve this question
10  
1) P=NP 2) none. –  Karolis Juodelė Dec 5 '12 at 16:55
3  
Comment of the year dude. –  Simon Hayward Dec 5 '12 at 17:08
    
Can you please explain it. Thanks –  user51905 Dec 5 '12 at 18:32
    
@KarolisJuodelė, you are the man. –  vermiculus Dec 13 '12 at 22:15
add comment

1 Answer

Your question (which belongs on CS.se, by the way) is asking the consequences of the Millennium Prize Problem $P = NP$.

This is an extremely difficult question to answer rigorously. Luckily, you're not being asked to prove it one way or the other - so you just need to concern yourself with what each of these mean.

In CS, there is a rather standard way of defining how 'hard' a given problem is. Every problem that is in $P$ is a problem that can be solved in polynomial time. That is, the best possible algorithm for the problem takes $O(t(n))$ time, where $t(n)$ is strictly polynomial in terms of $n$. For example,

$$t(n) = 1$$ $$t(n) = n$$ $$t(n) = n \log n$$ $$t(n) = n^2$$ $$t(n) = n^{42}$$ $$t(n) = n^{42}\log\log n$$

are all valid.

Here comes the important part. I'm sure you've noticed that it is usually much easier to check that an answer is correct than to come up with the answer yourself (For example, checking if a path is Hamiltonian or not.) This is (partly) what defines $NP$. $NP$ consists of all problems whose solutions can be verified in polynomial time. (Note that this implies $P \in NP$.) We know that, at worst, $NP$ problems can be solved in $2^{t(n)}$ time (see below). These problems are commonly solved via brute force, though not always. Thus, the question of $P = NP$ boils down to the following statement: is $NP$ in $P$? ($P \subseteq NP \land P \supseteq NP \implies P = NP$.) What does all that math mean? Well, if $NP \in P$, then any problem that can be verified in polynomial time can be solved in polynomial time. Proving this (I think) requires that an $NP$-complete problem be solved in polynomial time. If this were done, every $NP$ problem will be solved in $P$. (This is because $NP$ problems can be reduced to an $NP$-complete problem, and by definition, every $NP$-complete problem is reducible to every other $NP$-complete problem.)

Solving this question will make you a lot of money either way (a million if $\neq$, untold fortunes if $=$). If $P = NP$, RSA encrpytion would be moot (since primality testing is $NP$), TSP would be solved (since it's $NP$-complete), medicene would boon (protein folding is $NP$), and a host of other goodies would await us. It's a pretty big deal.


The reason they are called $P$ and $NP$ have to do with the Turing machine. If a problem can be solved in polynomial time on a deterministic (normal) Turing machine (DTM), than the problem is in $P$. If it can be solved in polynomial time on a non-deterministic Turing machine (NTM), then the problem is in $NP$. Converting an NTM to a DTM is proven to cause an exponential increase in time, namely $2^{t(n)}$ (this is due to the nature of sets and power sets). Thus, we have our exponential time complexity stuff. Algorithms that have classic NP solutions have time complexities such as $O(t(n))$ where

$$t(n) = 2^n$$ $$t(n) = 2^{n \log n}$$ $$t(n) = 2^{n^2}$$ $$t(n) = 2^{n^{42}}$$ $$t(n) = 2^{n^{42}\log\log n}.$$

These would all take incredibly long for (even moderately) large $n$. Performing such a reduction is significant.


It should be noted that if your reduction took exponential time, nothing is proven either way. That's the boring (yet ubiquitous) half of your question.

share|improve this answer
1  
that question does not belong on cstheory. That SE is only for research level questions. The question would be closed directly. –  sxd Dec 13 '12 at 16:50
1  
My bad, I was thinking about plain ole' CS when I wrote that. I tend to confuse the two a lot. Edited. –  vermiculus Dec 13 '12 at 22:07
add comment

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.