An Approach to P=NP via Descriptive Complexity
An approach to PNP based on descriptive complexity and HORNSAT
Alfred Horn was a logician who in 1951 discovered the important notion that we now call Horn clauses, in his honor. This class of special clauses has played a foundational role in the area of logic programming—for example, are a key part of the programming language Prolog. I used a picture of one of Horn’s PhD students, Dr. Ali Amir-Moez, who created the Horn-Moez Prize. I was unable to find a picture of Horn—even after a very long search—so I hope that this is okay.
Today I want to talk about an old idea, based on Horn clauses, that may be relevant to the P=NP question.
Years ago David Dobkin, Steven Reiss and I worked on a problem that used Horn Clauses. We proved that Linear Programming (LP) is complete for P with respect to logspace reductions—our proof used, in today’s terminology, an LP relaxation of Horn clauses. At the end of our paper we said:
This theorem is especially interesting since it is not known whether linear programming belongs to P or no? (see  for more details on this problem).
The reference “” was to a paper of Dobkin and Reiss that was in preparation; they had found many interesting problems that were equivalent to LP—all in a hope to better understand the problem. I think that they, and others, probably had guessed at the time that LP might be NP-complete, but I am not sure anymore what the conventional wisdom was at that time. Of course it still could be NP-complete, but that would imply that P is equal to NP.
Let’s turn to talking about Horn clauses and the P=NP problem. By the way this whole discussion is joint work with Ken Regan.
A Horn clause is a clause with at most one positive literal. Thus,
is a Horn clause, and
is not. A better way, for me at least, to think of Horn clauses is that the general form is:
where all the literals are positive.
The interest to logicians, like Horn, was that this class of clauses had certain model theoretic properties. For a theorist there are two reasons that they are interesting. First, a set of Horn clauses can be checked for satisfiability in polynomial time. The algorithm is just do the obvious: for clauses with just one variable, assign it so that the clause is true, and then keep applying the “implies” rules, until there are no more rules to apply. If you get and at some point, there is no assignment; otherwise there is one.
Second, SAT restricted to Horn clauses, HORNSAT, captures P. General SAT is NP; HORNSAT is P. Pretty neat. The intuition is simple: a Horn implication tells you what to do, while an implication like
allows a choice, which is exactly how general clauses encode nondeterminism.
The Descriptive Cook Theorem
In a previous discussion, I talked about descriptive complexity and its possible relationship to separation results. I will first review the notion, and then give a simple example of how it can be used.
Recall, instead of Kolmogorov’s general notion of the complexity of a string, which is based on Turing Machines (TM’s), we will use an intuitively weaker notion based on circuits.
Suppose that is a circuit and is a string. Say that describes if for all ,
We will use the size of the circuit to measure how complex the string is, and we call this the descriptive complexity of the string.
The following is a stronger version of Cook’s classic theorem, yet it uses essentially the same proof of his theorem:
Theorem: Let be a deterministic TM (DTM) that runs in polynomial time . Let be an input of length . Then, there are Horn clauses so that
- The clauses are satisfiable if and only if accepts .
- The descriptive complexity of is at most .
Even though the formulas typically arise from an time-space tableau of the computation, the layout of the tableau is so regular that we can easily describe the -th bit of the formula, given any . A descriptive complexity is enough to describe the formula. The point is that is not in the exponent.
If HORNSAT with low descriptive complexity can be solved by a low complexity witness, then . To be more precise, we need the following Hypothesis H:
Suppose that are Horn clauses . If they are satisfiable, then there is a valid assignment for the clauses with description complexity at most polynomial in the description complexity of the clauses.
The main result is this:
Theorem: Suppose that Hypothesis H is true. Then, .
Assume that Hypothesis H is true, and also that is true. One fact about is that it gives a fixed polynomial time overhead for simulating any NTM by a DTM . If runs in time , then can run in time . If is true, we can make a similar statement about an alternating Turing machine that makes a fixed finite number of alternations, though with a larger value of . We choose to work for ATMs that have an existential phase followed by a universal phase, i.e. “-machines.”
Now let be the exponent of the polynomial in Hypothesis H, and let be the exponent in the “” in the Descriptive Cook Theorem. Let . We will get a contradiction by speeding up any deterministic Turing machine that runs in time . Consider any input of length . Then, there is a collection of Horn clauses so that
- The clauses are satisfiable if and only if accepts .
- The descriptive complexity of is .
This follows by the Descriptive Cook Theorem. Now consider the ATM that on any input does the following:
- Construct a description of size for corresponding to on input .
- Guess a description of size for an assignment to the up-to- variables in .
- Branch over every Horn clause in . For each one, use the circuit to look up the values of the variables in . The branch returns true if is satisfied.
Thus accepts iff there exists a such that every branch returns true, which happens if and only if is satisfiable, which happens iff accepts . Hence . The running time of is bounded by times the maximum number of variables in our Horn clauses, which is constant. Finally from we get a DTM that simulates in time . Which is:
for some constant independent of . Since is a constant independent of , this is just . Thus we have sped up to a DTM running faster than , contradicting the time hierarchy theorem.
Relaxing a Little
If we could use just as the description complexity for the collection of Horn clauses, then we could relax the polynomial overhead in Hypothesis H to be an exponential function. That is, it could be a overhead so long as we can take small enough to cancel any given . This would illustrate the point that
an exponential upper bound, if used at logarithmic scaling, can help to give a polynomial lower bound.
As things stand, the Descriptive Cook Theorem actually gives , with the representing the dependence of the clauses on the input . Note that in the above proof the ATM is already given , so it does not need to unpack the “” part of the description. Hence if we formulate an appropriate notion of “conditional description complexity,” we can use it to formulate a relaxed version H’ of Hypothesis H that allows a bound, where is the conditional description complexity. More on this to come, and how it relates to the work on “computational depth” that was referenced in the previous discussion.
The key insight here is that an upper bound, Hypothesis H, can be used to prove that PNP. This fits into Regan’s and my philosophy that upper bounds are more likely to be possible, than proving lower bounds directly. The main open question is of course: is Hypothesis H true? Can we relate it to other open problems?