1
$\begingroup$

I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from every known hard problem to a possible hard problem. So, while proving the hardness of a problem, it does not matter which hard problem we pick, because there is a reduction from all of them. But, in practice it is always ideal to pick a problem for which the reduction is easy to obtain. For e.g., the reduction from Independent set to Vertex cover is straight away defined, where as the reduction from Hamiltonian cycle to Vertex cover is time consuming. So, i am wondering how do we know which hard problem to pick to prove the hardness for a given problem. Since, i am new to this area, i just want to know how does one go about proving the hardness of a problem.
TIA.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Experience and luck. But also having a list of NP-complete problems that you reduce from, and go through one by one exhaustively. Then, of course, you try to prove that the problem can be solved in polynomial time. Then you repeat.

You will, with experience, learn how to come up with gadgets that "propagate" information. The kind of gadget you need depends on the problem, and then you need to find out if the kind of gadget you need naturally fits into the problem you are reducing from.

Just the other day I was trying to find a polynomial time algorithm for a problem when I realized that it might be difficult. I immediately got a feeling that we could use hitting set or set cover to reduce from, and after a while I ended up with reducing from vertex cover, simply by understanding the problem better.

You should start compiling a list of NP-complete problems that you are familiar with, and these should contain Vertex Cover, Independent Set, Clique, Dominating Set, as well as Multicolored Clique and Multicolored Independent Set, 3-Coloring, SAT, 3-SAT, 1-in-3-SAT, Hamiltonian/Longest Cycle/Path, Feedback Vertex/Arc Set, 3D-Matching, Hitting Set, Set Cover, Max Cut, 3-Partition, etc. Go through every problem and ask how would I reduce from this problem.

Ps. these problems are just some of the problems I use. You might need a different list, and it might change throughout your career.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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