Polynomial time reductions and NP completeness

[@vi]

I unable to understand polynomial reduction. Here is the definition :

"A problem L1 reduces to L2 if and only if there is a way to solve L1 by deterministic polynomial time algorithm using a deterministic algorithms that solves L2 in polynomial time"

Is this is correct ? If yes, I would appreciate if someone can explain it to me.

Next, NP Hard :

"A problem L is NP-Hard if and only if satisfiability reduces to L

i.e. SAT < L "

But shouldn't it be L < SAT ? i.e. Reducing L to satisfiability ? Since we reduce L to satisfiability and since satisfiability is a known NP - Complete according to Cook, therefore we can conclude L as a NP-Hard ?

I would appreciate if someone can provide me some examples.

Thank you !

 

[abc.kb]

"A problem L1 reduces to L2 if and only if there is a way to solve L1 by deterministic polynomial time algorithm using a deterministic algorithms that solves L2 in polynomial time"

Is this is correct ? If yes, I would appreciate if someone can explain it to me.

A bit problematic. Here is the corrected version:

"A problem L1 has a polynomial time reduction to L2 if and only if there is a way to solve L1 by deterministic polynomial time algorithm using a deterministic algorithms that solves L2 in polynomial time".

The point is, the reduction should be "polynomial time reduction".


What is "polynomial time reduction" ?
A reduction is "polynomial time reduction" if given as input an instance of a problem of length m, it generates an instance of another problem in time O(m^i). Where i is an integer.

Remember that, when given an instance of a problem of length m, if the reduction takes time at most m^i for some integer i, then the output instance can't be longer than c.m^i for some constant c. When reducing a problem A to another problem B, to show B is at least as hard as A, always remember to use polynomial time reduction, otherwise you will possibly end up with a wrong conclusion. To know why, see section 10.1.5 of Hopcroft, Motwani, Ullman.

"A problem L is NP-Hard if and only if satisfiability reduces to L i.e. SAT < L "

^Correct.

But shouldn't it be L < SAT ? i.e. Reducing L to satisfiability ? Since we reduce L to satisfiability and since satisfiability is a known NP - Complete according to Cook, therefore we can conclude L as a NP-Hard ?

^Wrong. The only way to show some problem P is at least as hard as problem Q is to reduce Q to P. NOT P to Q. In other words, if you reduce(polynomially, of course) a problem A to a problem B, it does not mean A is harder than B. Rather, It means, B is at least as hard as A, that is B is either harder than A or equally hard as A but not easier than A. To prove a problem L is harder than SAT, you have to reduce SAT to L. Reduction of SAT to L is expressed as SAT < L.

 

[abc.kb]

No response in 20 days! I think the op has lost all interests in TOC.

 

[@vi]

LOL, no

I did not get any notification for the first reply. So I didn't check the thread.

Thank you very very much. These following two paragraphs explained easily.

Remember that, when given an instance of a problem of length m, if the reduction takes time at most m^i for some integer i, then the output instance can't be longer than c.m^i for some constant c. When reducing a problem A to another problem B, to show B is at least as hard as A

The only way to show some problem P is at least as hard as problem Q is to reduce Q to P. NOT P to Q. In other words, if you reduce(polynomially, of course) a problem A to a problem B, it does not mean A is harder than B. Rather, It means, B is at least as hard as A, that is B is either harder than A or equally hard as A but not easier than A. To prove a problem L is harder than SAT, you have to reduce SAT to L. Reduction of SAT to L is expressed as SAT < L.

This is what I wanted to know. Instead of referring numerous books & sites, I should have checked this thread

two more doubts :

*i.imgur.com/xDTK2.jpg

I have seen this diagram in almost every book, but no one says why there is no boundary for NP-H problems. Because are there infinitely many NPH problems out there ? Why cannot we draw like this ?

*i.imgur.com/ZJzef.jpg

Secondly, assume there is a problem in P. Now using that problem's solution if I solve a problem from NP, would that mean NP problem is reduced to P ? So that problem no longer would be in group of NP ?

and what happens other way around ? ASSUME, if I can solve a P problem using solution from a NP, then that would imply we have reduced P to NP ? Though it would be useless since we already have solution to P and we would be complicating it unnecessarily.

Thank you again

 

[abc.kb]

LOL, no

I did not get any notification for the first reply. So I didn't check the thread.

Thank you very very much. These following two paragraphs explained easily.





This is what I wanted to know. Instead of referring numerous books & sites, I should have checked this thread

two more doubts :

*i.imgur.com/xDTK2.jpg

I have seen this diagram in almost every book, but no one says why there is no boundary for NP-H problems. Because are there infinitely many NPH problems out there ? Why cannot we draw like this ?

*i.imgur.com/ZJzef.jpg

^We can't draw like the above cause, the complexity or hardness of NP-Hard problems are not limited. This figure from Wikipedia should clear the doubt.
Your reasoning that the NP-hard set is open because there are infinitely many NP-hard problems is wrong. Although the statement "there are infinitely many NP-hard problems" is indeed true, its not the reason for keeping the NP-hard set open. The figure you mentioned indicates the complexity of different classes of problems. It does not indicate how many problems are there in each set. In the wikipedia picture you will see that the vertical axis is labelled "complexity".

Secondly, assume there is a problem in P. Now using that problem's solution if I solve a problem from NP, would that mean NP problem is reduced to P ? So that problem no longer would be in group of NP ?

^Yes.
Suppose you have a problem in hand which is known to be in NP. Now, you write a program(to solve the problem in NP) which uses another problem(which is known to be in P) as subroutine. Now, if the whole program, including the subroutine runs in P and solves the NP problem in hand, you have just reduced the NP problem to a P problem. Although, you have not actually reduced the problem in formal sense,(reduction is a mathematical process), the way you use the P subroutine to solve the NP problem, is prefectly equivalent to reduction. Remember that, if the whole program(including the subroutine) runs in P, the reduction you did must be "polynomial time reduction". Otherwise, the whole program would not run in P. This is why "polynomial time reduction" is so important.
Yes, if you reduce a problem in NP to a problem in P, the problem is no longer in the class NP.

and what happens other way around ? ASSUME, if I can solve a P problem using solution from a NP, then that would imply we have reduced P to NP ? Though it would be useless since we already have solution to P and we would be complicating it unnecessarily.

Thank you again

You can always reduce a problem in P to a problem in NP. Doing so does not mean that the problem is in NP and not in P.
Suppose a problem has a linear time algorithm. Inventing a new exponential time algoritm for that problem does not prove that it is not solvable in linear time.

Hope it helps

 

[@vi]

^We can't draw like the above cause, the complexity or hardness of NP-Hard problems are not limited. This figure from Wikipedia should clear the doubt.
Your reasoning that the NP-hard set is open because there are infinitely many NP-hard problems is wrong. Although the statement "there are infinitely many NP-hard problems" is indeed true, its not the reason for keeping the NP-hard set open. The figure you mentioned indicates the complexity of different classes of problems. It does not indicate how many problems are there in each set. In the wikipedia picture you will see that the vertical axis is labelled "complexity".

That wiki image is really good, to understand. Just a simple image gives good explanation to my doubt & as well, what happens if N=NP. It also gave me clearer picture regarding NP-Complete problems. Thanks a lot for sharing !

I usually first go through Wiki, but I don't know how I missed this image. Probably I thought it'd be same as in all books.

^Yes.
Suppose you have a problem in hand which is known to be in NP. Now, you write a program(to solve the problem in NP) which uses another problem(which is known to be in P) as subroutine. Now, if the whole program, including the subroutine runs in P and solves the NP problem in hand, you have just reduced the NP problem to a P problem. Although, you have not actually reduced the problem in formal sense,(reduction is a mathematical process), the way you use the P subroutine to solve the NP problem, is prefectly equivalent to reduction. Remember that, if the whole program(including the subroutine) runs in P, the reduction you did must be "polynomial time reduction". Otherwise, the whole program would not run in P. This is why "polynomial time reduction" is so important.
Yes, if you reduce a problem in NP to a problem in P, the problem is no longer in the class NP.

Again, too simple explanation like earlier, very easy to understand !

You can always reduce a problem in P to a problem in NP. Doing so does not mean that the problem is in NP and not in P.
Suppose a problem has a linear time algorithm. Inventing a new exponential time algoritm for that problem does not prove that it is not solvable in linear time.

Hope it helps

Yes, it did !!