Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
basically a TM can compute any circuit that is constructed. but think, why do you use the term "artificial"? what can it mean in this context? then your actual question about NP complete problems being used to create other ones... its kind of general, but yes, thats the pt of NP completeness and also reducability of one NP complete problem into another. yes part of the whole point of reducibility is that it can be automated. – vzn Sep 17 '12 at 16:51
@vzn Thanks! I'm using artificial because we don't know whether the resulting problem "makes sense". You know, like a syntactically correct program that is semantically like "duh". The other thing is that it's machine-produced, so it's ok to call artificial I think. – saadtaame Sep 17 '12 at 16:59
there are some concepts of "artificial" in advanced CS, one of them relates to whether the circuit can be generated by a Turing machine after [x] amt of time, its called the uniform vs nonuniform distinction. however other concepts of "artificial" may be difficult or impossible to formalize. – vzn Sep 17 '12 at 17:23
@vzn, would you like to expand your comments into an answer? – Merbs Nov 29 '12 at 8:10
@merbs unf the question is related to some interesting questions in theory/research but is a bit too vague to answer in its current form... the theory of NP completeness & reductions is indeed basically about "creating existing NP complete problems to create other NP complete problems". also, a formula is finite in size so therefore, a TM to solve a single formula is trivial by complexity theory standards. the question is only interesting if one asks about infinite sets of formulas of unbounded size etc.... – vzn Dec 1 '12 at 20:03
up vote 2 down vote accepted

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.

share|cite|improve this answer
@ChrisPressy Wouldn't that result in gibberish problems? – saadtaame Jan 4 '13 at 21:16

Your Answer


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.