# Creating artificial NP-Complete problems

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?

-
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