Is Turing completeness monotone with respect to Cook reductions?

Question

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?

Answer 1

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.)

Answer 2

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.