# Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example:

The language of Boolean expressions is Turing complete; Does this imply that every NP-Complete language is Turing complete?

Or alternatively: The language of Horn clauses is Turing complete; Does this imply that every P-Hard language is Turing complete?

-
The term “Turing complete” is usually used for a computational model, not for a language. What do you mean by “The language of Boolean expressions is Turing complete”? –  Tsuyoshi Ito Jan 5 '12 at 14:31
I've added the [computability] tag because of the references to Turing completeness. –  r.e.s. Jan 5 '12 at 17:55
@TsuyoshiIto Oh, sorry, I guess I am sort of mixing terminology. What I meant is that the semantics of Boolean expressions is sufficient to express a Turing complete model of computation. –  Tim Seguine Jan 13 '12 at 20:30
@Tim, but it isn't, at least not in any conventional sense. You can say something like "for each size of the input there is a Boolean expression with that many variables which computes the output". But this is true for any function, whether or not it is computable. The distinction then becomes whether all of these various Boolean expressions are produced as a single computable function of the input size, so this just punts the question of "is this computable" to another level. –  Henning Makholm Jan 15 '12 at 1:25
I know what it means for a set to be Turing complete - it means the set can compute $\emptyset'$. No NP complete set is Turing complete in this sense, in fact every NP complete set is decidable. I also know what it means for a programming language to be "Turing complete", but I have no idea what it would mean for a programming language to be "NP complete". So I don't see how to answer the question without clarification. –  Carl Mummert Jan 12 '13 at 22:36

The question is a little confused, as the OP acknowledges, but it does have a straightforward answer in the context of complexity theory (although this answer might not be particularly illuminating for what the OP had in mind.)

The complexity class RE contains all languages (sets of strings) which can be enumerated by a Turing machine. There are RE-complete languages, such as the language of the Halting Problem (set of strings encoding Turing machines which halt). There is a fairly strong sense in which RE-completeness corresponds to Turing-completeness; a system is Turing-complete if it can enumerate the strings of an RE-complete language just as well as a Turing machine can.

On the other hand, the complexity class P (resp. NP) contains all languages which can be recognized by a Turing machine (resp. non-deterministic Turing machine) in polynomial time.

Both P and NP are known to be strictly contained within RE. That means there are languages in RE which are not in either P nor NP; therefore there is no P-complete or NP-complete language which is also RE-complete.

(P-hard is a different matter, because that only says that we know a language is at least as complex as a P-complete language; it could presumably be much more complex and in fact RE-complete.)

-
On the other hand, it seems that every RE-complete language (under certain polytime reductions) can be turned into a bounded NP-complete language in a straightforward way -- see cstheory.stackexchange.com/questions/1214/… –  Chris Pressey Dec 5 '12 at 9:57
This answer makes sense, but then I don't understand what is meant when people talk about horn clause logic being Turing complete. –  Tim Seguine Dec 5 '12 at 12:27
Sounds like they're being a bit flexible with the term (or, arguably, abusing it, depending on how they're using it.) A single boolean predicate (in horn clause form or otherwise) can't be Turing-complete, because it only has a finite number of inputs, whereas a Turing machine can accept an input of any length. But a countable family of boolean predicates, one for each input size (and defined in a constructive manner) could be Turing-complete. –  Chris Pressey Dec 5 '12 at 19:47
I guess you can't edit a comment more than once, so: the above should be "countably infinite", not just "countable", because finite sets are countable too (I guess!) and the important thing here is that it can't be a finite set. –  Chris Pressey Dec 6 '12 at 11:50
Okay, I understand the distinction. And it means that the original question isn't really well defined in the sense that I meant it. –  Tim Seguine Dec 7 '12 at 12:01

There is some truth in what you are implying, but you need to sort things out.

Let a boolean expression be a combination of binary variables, the operators AND $\land$ , OR $\lor$ and NOT $\neg$ and the constants 0 and 1.

Then, every computable function can be expressed as a boolean expression.

$SAT$ is defined as the set of satisfiable boolean expressions. The $\mathbb{NP}$-complete problem is to decide if a boolean formula, that is given as input, is satisfiable or not.

Now, let's combine the two. Every problem can be decided by a boolean formula that determines membership in the problem's language. The SAT problem is $\mathbb{NP}$-complete, therefore, every problem is $\mathbb{NP}$-complete.

The above proof is of course false, since no single complexity class, that sets bounds on resources, can contain all problems. So, where's the catch?

Suppose that you have an instance $a$ of a problem $A$. In order to convert it to a boolean formula, i.e. reduce it to $SAT$, a process must be followed. This process requires additional time, therefore this process combined with an algorithm for SAT does not yield a polynomial time non-deterministic algorithm for every problem, but only for problems in $\mathbb{NP}$.

Suppose that we are not interested in time, but in computability. So, we don't care how long the algorithm takes to convert any instance of any problem to a boolean formula, but if it can do so in finite time. Since we know that this is possible, a computation model using only boolean formulas is Turing equivalent and can compute any function computable by a Turing machine.

-
What do you mean by "every computable function can be expressed as a boolean expression"? A Boolean expression with $n$ can have only $2^n$ different inputs, but computable functions in general have infinitely many possible different inputs. How would you express, for example $x\mapsto x+1$ (for $x\in\mathbb N$) as a Boolean expression? –  Henning Makholm Jan 7 '12 at 17:40
@HenningMakholm Doesn't a computable function mean essentially "computable to any desired degree of accuracy"? In that case we can express any computable function as a family of boolean expressions parameterized by the precision. Any realizable computer has only finite memory, in which case it also can only accept a finite number of possible inputs; so I don't really understand the nature of your objection, since the Turing completeness of boolean expressions is (I thought) well established. A single Horn clause suffices to model a universal Turing machine. –  Tim Seguine Jan 13 '12 at 20:39
The sticking point seems to be that every decidable problem is reducible to 3SAT or HORNSAT, but maybe (probably) in superpolynomial time and space. Did I understand the gist of your answer correctly? –  Tim Seguine Jan 13 '12 at 20:45
@Tim, without further qualification the term "computable function" usually implies that the function takes a finite string of symbols (from a finite alphabet) as input and produces a similar string as output --- or some conventional equivalent of this, such as functions $\mathbb N\to\mathbb N$. In this model there is no speaking of "precision"; the function always computes its entire output for the given input in one go. There are generalizations that speak about things like real numbers (which in general need to be approximated), but these are not the standard meaning of the term. –  Henning Makholm Jan 15 '12 at 1:19
@HenningMakholm I am aware of this formulation. But it deosn't actually matter. That definition is equivalent to Turing computable, by the Church-Turing thesis. You are really splitting hairs here. –  Tim Seguine Jan 23 '12 at 9:36