Are there Conservation Laws in Complexity Theory?

Question

Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems.

Or take primality. It is easier to show composites in NP than primes in NP (which required Pratt) and eventually in P. Why did it have to display this asymmetry at all?

I know Hilbert, need for creativity, proofs are in NP etc. But that has not stopped me from having a queasy feeling that there is more to this than meets the eye.

Is there a quantifiable notion of "work" and is there a "conservation law" in complexity theory? That shows, for example, that even though CVP and LP are both P-complete, they hide their complexities at "different places" -- one in the reduction (Is CVP simple because all the work is done in the reduction?) and the other in expressibility of the language.

Anyone else queasy as well and with some insights? Or do we shrug and say/accept that this is the nature of computation?

This is my first question to the forum: fingers crossed.

Edit: CVP is Circuit Value Problem and LP is Linear Programming. Thanks Sadeq, for pointing out a confusion.

Answer 1

This is a question that has run across my mind many times.

I think one place to look is information theory. Here is a speculation of mine. Given a problem maybe we can give some sort of entropy value to information given as input and the information received from the algorithm. If we could do that, then there would be some minimum amount of information gain required by an algorithm to solve that problem.

There's one related thing I've wanted to figure out. In some NP-complete problems you can find a constrained version in P; with the Hamiltonian path if you specify that the graph is a DAG then there is a p-time algorithm to solve it. With other problems like TSP, there's often p-time algorithms that will approximate the optimal. It seems to me, for constrained p-time algorithms, there should be some proportional relationship between the addition information assumed and run-time complexity reduction. In the case of the TSP we aren't assuming additional information, we're relaxing the precision, which I expect to have a similar effect on any sort of algorithmic information gain.

Note on Conservation Laws

In the earlier 1900's there was little known German-American mathematician named Emily Noether. Among other things she was described by Einstein and Hilbert to be the most import women in the history of mathematics. In 1915 she published what is now known as Noether's First Theorem. The theorem was about physical laws of conservation, and said that all conservation laws have a corresponding differential symmetry in the physical system. Conservation of Angular Momentum comes from a rotational symmetry in space, Conservation of Linear Momentum is translation in space, Conservation of Energy is translation in time. Given that, for there to be some law of conservation of complexity in a formal sense, there would need to be some corresponding differential symmetry in a Langragian function.

Answer 2

I think the reason lies within the logical system we use. Each formal system has a set of axioms, and a set of rules of inference.

A proof in a formal system is just a sequence of formulae such that each formula in the sequence either is an axiom or is obtained from earlier formulae in the sequence by applying a rule of inference. A Theorem of the formal system is just the last formula in a proof.

The length of the proof of a theorem, assuming it is decidable in the logical system, depends totally on the sets of axioms and rules of inference.

For instance, consider the propositional logic, for which there exist several characterizations: Frege (1879), Nicod (1917), and Mendelson (1979). (See this short survey for more info.)

The latter system (Mendelson) has three axioms and one rule of inference (modus ponens). Given this short characterization, it is really hard to prove even the most trivial theorems, say $\varphi \to \varphi$. Here, by hard, I mean the minimum length of the proof is high.

This problem is termed proof complexity. To quote Beame & Pitassi:

One of the most basic questions of logic is the following: Given a universally true statement (tautology) what is the length of the shortest proof of the statement in some standard axiomatic proof system? The propositional logic version of this question is particularly important in computer science for both theorem proving and complexity theory. Important related algorithmic questions are: Is there an efficient algorithm that will produce a proof of any tautology? Is there an efficient algorithm to produce the shortest proof of any tautology? Such questions of theorem proving and complexity inspired Cook’s seminal paper on NP-completeness notably entitled “The complexity of theorem-proving procedures” and were contemplated even earlier by Gödel in his now well-known letter to von Neumann.

Answer 3

I was thinking about this same question the other day, when I was replaying some of Feynman's Lectures on Physics, and came to lesson 4 on the conservation of energy. In the lecture Feynman uses the example of a simple machine which (through some system of levers or pulleys or whatever) lowers a weight of one unit by some distance x, and uses that to lift a second weight of 3 units. How high can the weight be lifted? Feynman makes the observation that if the machine is reversible, then we don't need to know anything about the mechanism of the machine--we can treat it like a black box--and it will always lift the weight the maximum distance possible (x/3 in this case).

Does this have an analogue in computation? The idea of reversible computation brings to mind the work of Landauer and Bennett, but I'm not sure this is the sense of the term in which we are interested. Intuitively, if we have an algorithm for some problem that is optimal, then there isn't any wasted "work" being done churning bits; while a brute-force approach to the same problem would be throwing away CPU cycles left and right. However, I imagine one could construct a physically reversible circuit for either algorithm.

I think the first step in approaching a conservation law for computational complexity is to figure out exactly what should be conserved. Space and time are each important metrics, but it's clear from the existence of space/time trade-offs that neither one by itself is going to be adequate as a measure of how much "work" is being done by an algorithm. There are other metrics such as TM head reversals or tape cell crossings that have been used. None of these really seems to be close to our intuition of the amount of "work" required to carry out a computation.

The flip side of the problem is figuring out just what that work gets converted into. Once you have the output from a program, what exactly is it that you have gained?

Answer 4

Some observations suggesting the existence of conservation law:

If we consider polynomial-time (or log-space) computable reductions $<_p$ as transformations between computational problems, then the following definitions of known complexity classes suggest the existence of some conserved property under "efficient" transformations. Assuming $P\ne NP$ then "hardness" seems to be the conserved property.

$P=\{L| L<_p HornSAT \}$

$NP=\{L| L<_p 3SAT \}$

$CoNP=\{L| \bar L<_p 3SAT \}$

$NPC=\{L| L<_p 3SAT, 3SAT<_p L \}$

$PC=\{L| L<_p HornSAT, HornSAT<_p L \}$

EDIT: $P$ is more accurately defined as $P=\{L| L<_p HornSAT, \bar L <_p HornSAT \}$ suggesting that the hardness of problems in $P$ is invariant under complement operation while it is not known that complementation preserves the hardness of $NP$ problems (unless $P=NP$).

Answer 5

Tao suggests the existence of law of conservation of difficulty in mathematics: "in order to prove any genuinely non-trivial result, some hard work has to be done somewhere".

He argues that the difficulty of some mathematical proofs suggests a lower bound to the amount of effort needed by the theorem proving process.