<p>This is a question that has run across my mind many times.</p>

<p>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.</p>

<p>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.</p>

<p><strong>Note on Conservation Laws</strong></p>

<p>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 <a href="http://en.wikipedia.org/wiki/Noether%27s_theorem">Noether's First Theorem</a>.  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.</p>

CC BY-SA 2.5
2010-11-18T03:22:37.067Z
+1 Great answer! I have often had similar musings (@MattRS: send me an email). By the way, I don't think Emmy Noether is "little-known," but in fact quite the opposite, although maybe she's not well-known in TCS.  Noether's First Theorem is well-known to physicists, and Noetherian rings are a central object of study in commutative algebra and algebraic geometry.  Several other important theorems, mostly in those areas, also bear her name.
Joshua Grochow
CC BY-SA 2.5
2010-11-18T04:33:56.983Z
Yeah thats what I meant; not well known to comp sci.  I always thought abstract algebra should be more widely taught in CS.
MattRS
CC BY-SA 3.0
2011-07-28T05:40:47.443Z
Even though this argument is compelling, I wonder if is it compatible with many problems having a sharp approximability threshold. (By this, I mean a problem such that achieving an approximation factor $\alpha > 1$ is easy, but $\alpha - \epsilon$ is hard for all $\epsilon > 0$.) Why is the relation between the precision required and the algorithmic information gain so dramatically discontinuous?
Srivatsan Narayanan
CC BY-SA 2.5
2010-11-17T19:27:45.830Z
2010-11-17T19:27:45.830Z
MattRS
<p>I think the reason lies within the logical system we use. Each formal system has a set of <em>axioms</em>, and a set of <em>rules of inference</em>. </p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>For instance, consider the propositional logic, for which there exist several characterizations: Frege (1879), Nicod (1917), and Mendelson (1979). (See this <a href="http://www.trinity.edu/cbrown/logic/alter.pdf">short survey</a> for more info.) </p>

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

<p>This problem is termed <a href="http://en.wikipedia.org/wiki/Proof_complexity">proof complexity</a>. To quote <a href="http://www.cs.toronto.edu/~toni/Papers/survey.ps">Beame &amp; Pitassi</a>:</p>

<blockquote>
  <p>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 eﬃcient algorithm that will produce a proof of any
  tautology? Is there an eﬃcient 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.</p>
</blockquote>

CC BY-SA 2.5
2010-11-17T03:58:26.247Z
2010-11-17T03:58:26.247Z
Sadeq Dousti
<p>I was thinking about this same question the other day, when I was replaying some of Feynman's Lectures on Physics, and came to <a href="http://student.fizika.org/~jsisko/Knjige/Opca%20Fizika/Feynman%20Lectures%20on%20Physics/Vol%201%20Ch%2004%20-%20Conservation%20of%20Energy.pdf">lesson 4</a> 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).</p>

<p>Does this have an analogue in computation?  The idea of <a href="http://en.wikipedia.org/wiki/Reversible_computing">reversible computation</a> 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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2010-11-17T20:07:35.377Z
2010-11-17T20:07:35.377Z
Kurt
<p>Some observations suggesting the existence of conservation law:</p>

<p>If we consider polynomial-time (or log-space) computable reductions $&lt;_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>

<p>$P=\{L| L&lt;_p HornSAT \}$ </p>

<p>$NP=\{L| L&lt;_p 3SAT \}$
</p>

<p>$CoNP=\{L| \bar L&lt;_p 3SAT \}$
</p>

<p>$NPC=\{L| L&lt;_p 3SAT, 3SAT&lt;_p L \}$
</p>

<p>$PC=\{L| L&lt;_p HornSAT, HornSAT&lt;_p L \}$
</p>

<p><strong>EDIT</strong>: $P$ is more accurately defined as $P=\{L| L&lt;_p HornSAT, \bar L &lt;_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$).</p>

CC BY-SA 2.5
2010-11-17T12:42:51.230Z
2010-11-17T13:35:19.313Z
2010-11-17T13:35:19.313Z
Mohammad Al-Turkistany
<p>Tao suggests the existence of <a href="http://terrytao.wordpress.com/career-advice/be-sceptical-of-your-own-work/" rel="nofollow">law of conservation of difficulty</a> in mathematics: "in order to prove any genuinely non-trivial result, some hard work has to be done somewhere".</p>

<p>He argues that the <a href="http://terrytao.wordpress.com/career-advice/be-sceptical-of-your-own-work/" rel="nofollow">difficulty of some mathematical proofs</a> suggests a lower bound to the amount of effort needed by the theorem proving process.</p>

CC BY-SA 3.0
2014-06-28T18:18:01.070Z
2014-06-28T18:18:01.070Z
Mohammad Al-Turkistany
<p>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. </p>

<p>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? </p>

<p>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.</p>

<p>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.</p>

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

<p>This is my first question to the forum: fingers crossed.</p>

<p><strong>Edit:</strong> CVP is <em>Circuit Value Problem</em> and LP is <em>Linear Programming.</em>  Thanks Sadeq, for pointing out a confusion.</p>

CC BY-SA 3.0
2011-07-28T05:43:59.327Z
@AaronS Can you give some references for this computational depth concept?
Srivatsan Narayanan
CC BY-SA 3.0
2011-07-28T15:42:38.663Z
@Srivatsan: Bennett's original paper is [here](http://www.research.ibm.com/people/b/bennetc/UTMX.pdf). The theorems are true, but many of the proofs are informal.  Lutz and Lathrop reproved several of Bennett's theorems more rigorously, and obtained new results, in [this paper](http://www.cs.iastate.edu/~lutz/=PAPERS/rcd.ps) (postscript file). Fortnow and co-authors have explored a slightly different notion of depth. Section 7.7 of the third edition of Li and Vitanyi's Komolgorov Complexity book provides a survey of the area.
Aaron Sterling
CC BY-SA 4.0
2024-05-16T06:01:08.287Z
Isn't this notion of hardness captured by the weakest reductions under which a problem is hard for a given complexity class ? For instance CVP is probably not P-hard under as weak reductions as LP. Similarly COMPOSITES may reduce to PRIMES with a reduction under which PRIMES does not to COMPOSITES. Then you can define an invariant or semiinvariant, under appropriate maps, $I_R(L)$ of $L$ for each reduction $R$: the set of languages $\leq_RL$. It would hold that $I$(CVP)<$I$(LP). We can also formulate an information version of that, similar to AIT. I may check some examples of reductions.
plm
CC BY-SA 2.5
2010-11-16T20:05:14.223Z
At first, I mistook CVP for *Closest Vector Problem* (which is NP-hard). Then I noted that it is the *Circuit Value Problem*. I thought it would be helpful to mention this.
Sadeq Dousti
CC BY-SA 2.5
2010-11-16T23:29:30.347Z
interesting question. Not sure there's an interesting answer though :)
Suresh Venkat
CC BY-SA 2.5
2010-11-16T23:44:58.863Z
I have been wondering for longtime about the possibility of characterization of efficient computation in term of a conserved quantity under every "efficient" algorithm.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-17T04:05:23.313Z
Just an observation: The difficulty of proving the membership to NP (say) is not a property of a language, but a property of a _description_ of a language.  For example, it requires some effort to prove that the set of primes is in NP, but it is trivial that the set of integers having a Pratt certificate is in NP.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T04:39:42.620Z
Is time-space tradeoff lowerbounds not applicable as a conservation law in the sense of the wording of this question?
Maverick Woo
CC BY-SA 2.5
2010-11-17T13:38:57.197Z
Charles Bennett's notion of computational depth (originally "logical depth") may capture part of the intuition of "work required to demonstrate a complexity fact."
Aaron Sterling
<cc.complexity-theory><big-picture>
Are there Conservation Laws in Complexity Theory?
V Vinay
# Are there Conservation Laws in Complexity Theory?

(Asked by: username_0 on 2010-11-16)

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.

**Tags:** cc.complexity-theory, big-picture

> **Comments:**
> **username_4**: At first, I mistook CVP for *Closest Vector Problem* (which is NP-hard). Then I noted that it is the *Circuit Value Problem*. I thought it would be helpful to mention this.  
> **username_5**: interesting question. Not sure there's an interesting answer though :)  
> **username_6**: I have been wondering for longtime about the possibility of characterization of efficient computation in term of a conserved quantity under every "efficient" algorithm.  
> **username_7**: Just an observation: The difficulty of proving the membership to NP (say) is not a property of a language, but a property of a _description_ of a language.  For example, it requires some effort to prove that the set of primes is in NP, but it is trivial that the set of integers having a Pratt certificate is in NP.  
> **username_8**: Is time-space tradeoff lowerbounds not applicable as a conservation law in the sense of the wording of this question?  
> **username_2**: Charles Bennett's notion of computational depth (originally "logical depth") may capture part of the intuition of "work required to demonstrate a complexity fact."  
> **username_1**: @AaronS Can you give some references for this computational depth concept?  
> **username_2**: @Srivatsan: Bennett's original paper is [here](http://www.research.ibm.com/people/b/bennetc/UTMX.pdf). The theorems are true, but many of the proofs are informal.  Lutz and Lathrop reproved several of Bennett's theorems more rigorously, and obtained new results, in [this paper](http://www.cs.iastate.edu/~lutz/=PAPERS/rcd.ps) (postscript file). Fortnow and co-authors have explored a slightly different notion of depth. Section 7.7 of the third edition of Li and Vitanyi's Komolgorov Complexity book provides a survey of the area.  
> **username_3**: Isn't this notion of hardness captured by the weakest reductions under which a problem is hard for a given complexity class ? For instance CVP is probably not P-hard under as weak reductions as LP. Similarly COMPOSITES may reduce to PRIMES with a reduction under which PRIMES does not to COMPOSITES. Then you can define an invariant or semiinvariant, under appropriate maps, $I_R(L)$ of $L$ for each reduction $R$: the set of languages $\leq_RL$. It would hold that $I$(CVP)<$I$(LP). We can also formulate an information version of that, similar to AIT. I may check some examples of reductions.  

---

## 5 answers

### Answer by username_9 on 2010-11-17. Score: 13

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](http://en.wikipedia.org/wiki/Noether%27s_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.

> **Comments:**
> **username_10**: +1 Great answer! I have often had similar musings (@username_9: send me an email). By the way, I don't think Emmy Noether is "little-known," but in fact quite the opposite, although maybe she's not well-known in TCS.  Noether's First Theorem is well-known to physicists, and Noetherian rings are a central object of study in commutative algebra and algebraic geometry.  Several other important theorems, mostly in those areas, also bear her name.  
> **username_9**: Yeah thats what I meant; not well known to comp sci.  I always thought abstract algebra should be more widely taught in CS.  
> **username_1**: Even though this argument is compelling, I wonder if is it compatible with many problems having a sharp approximability threshold. (By this, I mean a problem such that achieving an approximation factor $\alpha > 1$ is easy, but $\alpha - \epsilon$ is hard for all $\epsilon > 0$.) Why is the relation between the precision required and the algorithmic information gain so dramatically discontinuous?  

---

### Answer by username_4 on 2010-11-17. Score: 6

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](http://www.trinity.edu/cbrown/logic/alter.pdf) 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](http://en.wikipedia.org/wiki/Proof_complexity). To quote [Beame & Pitassi](http://www.cs.toronto.edu/~toni/Papers/survey.ps):

> 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 eﬃcient algorithm that will produce a proof of any
> tautology? Is there an eﬃcient 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 by username_11 on 2010-11-17. Score: 5

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](http://student.fizika.org/~jsisko/Knjige/Opca%20Fizika/Feynman%20Lectures%20on%20Physics/Vol%201%20Ch%2004%20-%20Conservation%20of%20Energy.pdf) 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](http://en.wikipedia.org/wiki/Reversible_computing) 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 by username_6 on 2010-11-17. Score: 2

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 by username_6 on 2014-06-28. Score: 1

Tao suggests the existence of [law of conservation of difficulty](http://terrytao.wordpress.com/career-advice/be-sceptical-of-your-own-work/) 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](http://terrytao.wordpress.com/career-advice/be-sceptical-of-your-own-work/) suggests a lower bound to the amount of effort needed by the theorem proving process.


---

