Cheap and Secure Web Hosting Provider : See Now

[Solved]: Creating artificial NP-Complete problems

, , No Comments
Problem Detail: 

Stephen Cook's proof of the NP-completeness of SAT is constructive. Given a Turing machine $M$, one can create a logical formula that is satisfiable if and only if $M$'s computation halts in an accepting state. This suggests that we could take a logical formula and create a Turing machine $M'$ whose computation is described by that formula, thereby creating an artificial problem solved by $M'$. Is it possible to use existing NP-complete problems to create other NP-complete problems? Can this be automated?

Asked By : saadtaame

Answered By : Chris Pressey

Dodging any questions about whether this is "interesting" or "artificial" (or whether Computer Science really needs any more NP-complete problems than it already has), the answer is "yes". Pick a structure-preserving mapping between some set of strings and problem instances of 3SAT. Show that the mapping can be computed in polynomial time (i.e., it is a polytime reduction). Then, deciding if a string is in your set of strings is NP-complete. Repeat as desired (the composition of polytime reductions is a polytime reduction.)

If you wanted to automate this process of creating new NP-complete problems, then it would likely be more efficient to construct the mappings from some base set of polytime mappings, using methods known to preserve polynomial time, rather than picking an arbitrary mapping and proving that it is a polytime reduction.

Note that this is not quite what you suggest in your question. You can take a logical formula and build a Turing machine corresponding to it, but that in itself doesn't lead to an NP-complete problem. For instance, 2SAT instances can be decided in polynomial time. And a particular formula will only correspond to a particular machine, whereas you need a set of formulas (or machines) to define a complexity class; so to make new problems in NPC, you really need to show how one set can be converted into another (i.e. a polytime reduction), even if your sets are sets of logical formulas.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback