Is it correct to say that give a solution (with any time complexity) to an NP-Complete problem it can be modified in some way so that it can solve all NP-Complete problems? If yes, then how can that be done?
Asked
Active
Viewed 111 times
1 Answers
0
Yes, any NP problem can be reduced to an NP-complete problem and all NP-complete problems can be reduced to each other, all in polynomial time. You can solve a different NP problem by reducing it to an instance of an NP-complete problem.
Boolean Satisfiability is a natural and expressive NP-complete target for such reductions. Take the instance of the NP problem you're trying to solve and create a Boolean circuit that takes some number of bits as input to the problem and verifies that the bits constitute a correct answer. Once you have the valid circuit it suffices to do a Tseitin transformation on it and then ask whether the resulting Boolean formula is satisfiable.
For example, to use Boolean Satisfiability to ask whether some $n$-bit number has a factor other than itself and 1, construct a circuit that multiplies two $n/2$ bit numbers together. Leave the values of the input bits unspecified and hardcode the output bits to match $n$'s bits. Tseitin-transform the circuit into a Boolean formula. If the formula is satisfiable then there is such a factor, otherwise there isn't one.
Kyle Jones
- 1,871