<p>In a weird way, the PCP theorem itself is a good example of proving a lower bound via an upper bound. An "efficient" randomized strategy for verifying a proof using a constant number of probes of the proof and only $\log n$ random bits leads to a lower bound for approximating the number of satisfied clauses in an instance of 3SAT. </p>

CC BY-SA 2.5
2010-11-23T13:08:37.013Z
If you count NP-hardness (as opposed to separation from a class) as lower bounds, you do not need the PCP theorem; _reductions_ are efficient algorithms which prove that some problems are hard.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-23T17:10:58.713Z
that's a good point, Tsuyoshi. However, NP-hardness reductions are "direct". show that solving an unknown problem solves a known hard problem. Some of the examples given here are more indirect. But this is subjective of course.
Suresh Venkat
CC BY-SA 2.5
2010-11-23T19:15:09.943Z
The very statement of the PCP theorem is the NP-completeness of Gap-3SAT.  Moreover, I do not know what you meant by claiming that the PCP theorem is indirect.  It is true that the PCP theorem requires one of the most complicated proofs among NP-completeness results, but is it a good thing?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-29T05:27:00.610Z
Suresh, Could you please post here, as a new answer, an expanded version of the two examples you referenced in your answer to the other question (Meyer's result and GCT)?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-29T06:51:35.187Z
any reason why ? I don't have a problem doing so, but is it necessary since you cite it in the question ?
Suresh Venkat
CC BY-SA 2.5
2010-11-23T07:15:05.027Z
2010-11-23T07:15:05.027Z
Suresh Venkat
<p>The incompressibility method is a method based on Kolmogorov complexity to prove lower bounds. One of the first application of this method was to prove that recognizing palindromes on a Turing machine with a single tape requires quadratic time. </p>

<p>Loosely speaking, the idea of this method is to describe a procedure to find an input using the information contained in the run of an algorithm solving the problem we consider on this input. The better is the procedure, the higher is the lower bound on the original problem.</p>

<p>Of course, full details can be found in <a href="http://homepages.cwi.nl/~paulv/kolmogorov.html">the textbook of Li and Vitanyi</a>.</p>

CC BY-SA 2.5
2010-11-21T22:37:07.017Z
2010-11-21T22:37:07.017Z
Marc
<p>For the "lower bound via upper bound" question you asked:</p>

<p>The STOC 2010 paper "How to Compress Interactive Communication" <a href="http://www.cs.princeton.edu/~boaz/Papers/directsum.pdf">[BBCR10]</a> arrives at an improved direct sum theorem for randomized communication complexity by demonstrating an improved compression protocol for interactive communication.</p>

<p>Specifically, given two parties computing some joint function of their mutual inputs (i.e. an interactive computation scenario), they show that any protocol that communicates $C$ bits and reveals $I$ bits of new information to the parties involved can be simulated by a new protocol using $\tilde O(\sqrt{CI})$ bits -- the improved upper bound.</p>

<p>As a consequence of this improved protocol compression, they show that in the worst case: Given any function $f$ that takes $n$ time to compute individually, computing $k$ copies of $f$ requires at least $\sqrt{k} \cdot n$ time -- the improved lower bound.</p>

CC BY-SA 2.5
2010-11-23T13:41:29.430Z
2010-11-23T13:41:29.430Z
Daniel Apon
<p>This is somehow different from what you asked, but since it is related, I thought I could mention it.</p>

<p><a href="http://portal.acm.org/citation.cfm?id=803400">Carter &amp; Wegman (1977)</a> introduced the notion of <strong>universal hashing</strong>. The notion was used in numerous papers (<a href="http://portal.acm.org/citation.cfm?id=808762">Sipser (1983)</a>, <a href="http://portal.acm.org/citation.cfm?id=808740">Stockmeyer (1983)</a>, <a href="http://portal.acm.org/citation.cfm?id=22192">Babai (1985)</a>, and <a href="http://portal.acm.org/citation.cfm?id=12137">Goldwasser &amp; Sipser (1986)</a>) to prove <strong>approximate lower bounds</strong>.</p>

<p>This was until 1987, in which <a href="http://portal.acm.org/citation.cfm?id=28418">Fortnow</a> made use of the <em>universal hashing</em> to prove <strong>approximate upper bounds</strong>. (In fact, to provide a protocol for proving approximate upper bounds.)</p>

<hr>

<h3>Edit:</h3>

<p>These are not lower-bound results, but they might be useful anyway:</p>

<p>$\rm{NP} \subset \rm{P/poly} \quad \Rightarrow \quad \rm{PH}=\rm{\Sigma_2^p}=\rm{\Pi_2^p}$
</p>

<p>$\rm{NP} \subset \rm{P/poly} \quad \Rightarrow \quad \rm{AM}=\rm{MA}$
</p>

<p>$\rm{coNP} \subset \rm{NP/poly} \quad \Rightarrow \quad \rm{PH}=\rm{\Sigma_3^p}=\rm{\Pi_3^p}$</p>

CC BY-SA 2.5
2010-11-21T19:47:34.733Z
2010-11-21T22:06:33.390Z
2010-11-21T22:06:33.390Z
Sadeq Dousti
<p>Here is an example from Computational Complexity: A Modern Approach by Arora and Barak (page 128):</p>

<p>If every language in $EXP$ has circuits of size $o(2^{n} /n)$ then $P \ne NP$  </p>

CC BY-SA 2.5
2010-12-08T05:15:38.750Z
2010-12-08T05:15:38.750Z
Mohammad Al-Turkistany
<p>I found a nice example in Dick Lipton's blog, <a href="http://rjlipton.wordpress.com/2010/01/05/an-approach-to-pnp-via-descriptive-complexity/" rel="noreferrer">An Approach to P=NP via Descriptive Complexity</a>, He proposes an upper bound conjecture (Hypothesis H) that would imply <span class="math-container">$P\ne NP$</span>.</p>
<blockquote>
<p><strong>Hypothesis H</strong>: Suppose that <span class="math-container">$C$</span> are Horn clauses <span class="math-container">$C_{1} \wedge \dots \wedge C_{m}$</span>. 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.</p>
<p><strong>Theorem</strong>: Suppose that Hypothesis H is true. Then, <span class="math-container">$P \ne NP$</span></p>
</blockquote>

CC BY-SA 2.5
2010-11-25T17:11:04.113Z
2010-11-25T17:11:04.113Z
2020-06-17T09:38:08.363Z
Mohammad Al-Turkistany
<p>One could turn the question around and ask what lower bounds <em>aren't</em> proved by proving an upper bound. Almost all communication complexity lower bounds (and streaming algorithm lower bound and data structure lower bounds that rely on communication complexity arguments) are proved by showing that a communication protocol can be constructively turned into an encoding scheme, with the length of the encoding depending on the communication complexity of the protocol, and the lower bound for the protocol follows from the fact that you cannot encode all n bit messages using n-1 bits or fewer.</p>

<p>The Razborov-Smolensky circuit lower bounds work by showing how to simulate bounded-depth circuits by low-degree polynomials.</p>

<p>A couple of candidates of lower bounds that are not proved with an upper bound could be the time hierarchy theorem (although, to get the tightest bounds, one needs an efficient universal turing machine, which is a non-trivial algorithmic task) and the proof of AC0 lower bounds using the switching lemma (but the cleanest proof of the switching lemma uses a counting/incompressibility/Kolmogorov-complexity)</p>

CC BY-SA 2.5
2010-11-28T21:29:04.377Z
Interesting, that's a great summary of communication complexity lower bounds! Another (odd?) candidate: Ladner's theorem/diagonalization. The bounds, of course, are not specified (nor even the problem(s)!), but it does show a superpolynomial lower bound for some problem. Of course, this assumes P$\ne$NP, which could conceivably be proved with an upper bound, a la GCT...
Daniel Apon
CC BY-SA 2.5
2010-11-28T20:43:01.623Z
2010-11-28T21:57:52.447Z
2010-11-28T21:57:52.447Z
Luca Trevisan
<p>The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to this question, <a href="https://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science/2914#2914">Are there any counter-intuitive results in theoretical computer science?</a>, provided two examples of establishing lower-bounds by proving upper-bounds.</p>

<blockquote>
  <ul>
  <li><p>What are the other interesting results for proving complexity lower-bounds that was obtained by proving complexity upper-bounds? </p></li>
  <li><p>Is there any upper-bound conjecture that would imply $NP \not\subseteq P/poly$ (or $P \ne NP$)? </p></li>
  </ul>
</blockquote>

CC BY-SA 2.5
2010-11-21T17:59:30.857Z
Should this be a CW?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-21T19:32:14.253Z
I like it as is (not CW), but I believe it is a `[soft-question]`.
Sadeq Dousti
CC BY-SA 2.5
2010-11-22T02:23:29.253Z
@Sadeq: don't think this is a soft question, this is precise enough to have a clear answer.
Kaveh
CC BY-SA 2.5
2010-11-29T04:47:32.813Z
Meyer's result pointed out by Suresh shows that the existence of polynomial circuits for $EXP$ would prove $P \ne NP$.
Mohammad Al-Turkistany
<cc.complexity-theory><lower-bounds>
Proving lower bounds by proving upper bounds
Mohammad Al-Turkistany
# Proving lower bounds by proving upper bounds

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

The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. username_3 in his answer to this question, [Are there any counter-intuitive results in theoretical computer science?](https://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science/2914#2914), provided two examples of establishing lower-bounds by proving upper-bounds.

> * What are the other interesting results for proving complexity lower-bounds that was obtained by proving complexity upper-bounds?
> * Is there any upper-bound conjecture that would imply $NP \not\subseteq P/poly$ (or $P \ne NP$)?

**Tags:** cc.complexity-theory, lower-bounds

> **Comments:**
> **username_0**: Should this be a CW?  
> **username_1**: I like it as is (not CW), but I believe it is a `[soft-question]`.  
> **username_2**: @Sadeq: don't think this is a soft question, this is precise enough to have a clear answer.  
> **username_0**: Meyer's result pointed out by Suresh shows that the existence of polynomial circuits for $EXP$ would prove $P \ne NP$.  

---

## 7 answers

### Answer by username_7 on 2010-11-28. Score: 24 | Accepted answer

One could turn the question around and ask what lower bounds *aren't* proved by proving an upper bound. Almost all communication complexity lower bounds (and streaming algorithm lower bound and data structure lower bounds that rely on communication complexity arguments) are proved by showing that a communication protocol can be constructively turned into an encoding scheme, with the length of the encoding depending on the communication complexity of the protocol, and the lower bound for the protocol follows from the fact that you cannot encode all n bit messages using n-1 bits or fewer.

The Razborov-Smolensky circuit lower bounds work by showing how to simulate bounded-depth circuits by low-degree polynomials.

A couple of candidates of lower bounds that are not proved with an upper bound could be the time hierarchy theorem (although, to get the tightest bounds, one needs an efficient universal turing machine, which is a non-trivial algorithmic task) and the proof of AC0 lower bounds using the switching lemma (but the cleanest proof of the switching lemma uses a counting/incompressibility/Kolmogorov-complexity)

> **Comments:**
> **username_6**: Interesting, that's a great summary of communication complexity lower bounds! Another (odd?) candidate: Ladner's theorem/diagonalization. The bounds, of course, are not specified (nor even the problem(s)!), but it does show a superpolynomial lower bound for some problem. Of course, this assumes P$\ne$NP, which could conceivably be proved with an upper bound, a la GCT...  

---

### Answer by username_3 on 2010-11-23. Score: 14

In a weird way, the PCP theorem itself is a good example of proving a lower bound via an upper bound. An "efficient" randomized strategy for verifying a proof using a constant number of probes of the proof and only $\log n$ random bits leads to a lower bound for approximating the number of satisfied clauses in an instance of 3SAT.

> **Comments:**
> **username_4**: If you count NP-hardness (as opposed to separation from a class) as lower bounds, you do not need the PCP theorem; _reductions_ are efficient algorithms which prove that some problems are hard.  
> **username_3**: that's a good point, Tsuyoshi. However, NP-hardness reductions are "direct". show that solving an unknown problem solves a known hard problem. Some of the examples given here are more indirect. But this is subjective of course.  
> **username_4**: The very statement of the PCP theorem is the NP-completeness of Gap-3SAT.  Moreover, I do not know what you meant by claiming that the PCP theorem is indirect.  It is true that the PCP theorem requires one of the most complicated proofs among NP-completeness results, but is it a good thing?  
> **username_0**: Suresh, Could you please post here, as a new answer, an expanded version of the two examples you referenced in your answer to the other question (Meyer's result and GCT)?  
> **username_3**: any reason why ? I don't have a problem doing so, but is it necessary since you cite it in the question ?  

---

### Answer by username_5 on 2010-11-21. Score: 12

The incompressibility method is a method based on Kolmogorov complexity to prove lower bounds. One of the first application of this method was to prove that recognizing palindromes on a Turing machine with a single tape requires quadratic time.

Loosely speaking, the idea of this method is to describe a procedure to find an input using the information contained in the run of an algorithm solving the problem we consider on this input. The better is the procedure, the higher is the lower bound on the original problem.

Of course, full details can be found in [the textbook of Li and Vitanyi](http://homepages.cwi.nl/~paulv/kolmogorov.html).


---

### Answer by username_6 on 2010-11-23. Score: 11

For the "lower bound via upper bound" question you asked:

The STOC 2010 paper "How to Compress Interactive Communication" [[BBCR10]](http://www.cs.princeton.edu/~boaz/Papers/directsum.pdf) arrives at an improved direct sum theorem for randomized communication complexity by demonstrating an improved compression protocol for interactive communication.

Specifically, given two parties computing some joint function of their mutual inputs (i.e. an interactive computation scenario), they show that any protocol that communicates $C$ bits and reveals $I$ bits of new information to the parties involved can be simulated by a new protocol using $\tilde O(\sqrt{CI})$ bits -- the improved upper bound.

As a consequence of this improved protocol compression, they show that in the worst case: Given any function $f$ that takes $n$ time to compute individually, computing $k$ copies of $f$ requires at least $\sqrt{k} \cdot n$ time -- the improved lower bound.


---

### Answer by username_1 on 2010-11-21. Score: 6

This is somehow different from what you asked, but since it is related, I thought I could mention it.

[Carter & Wegman (1977)](http://portal.acm.org/citation.cfm?id=803400) introduced the notion of **universal hashing**. The notion was used in numerous papers ([Sipser (1983)](http://portal.acm.org/citation.cfm?id=808762), [Stockmeyer (1983)](http://portal.acm.org/citation.cfm?id=808740), [Babai (1985)](http://portal.acm.org/citation.cfm?id=22192), and [Goldwasser & Sipser (1986)](http://portal.acm.org/citation.cfm?id=12137)) to prove **approximate lower bounds**.

This was until 1987, in which [Fortnow](http://portal.acm.org/citation.cfm?id=28418) made use of the *universal hashing* to prove **approximate upper bounds**. (In fact, to provide a protocol for proving approximate upper bounds.)

---

### Edit:

These are not lower-bound results, but they might be useful anyway:

$\rm{NP} \subset \rm{P/poly} \quad \Rightarrow \quad \rm{PH}=\rm{\Sigma\_2^p}=\rm{\Pi\_2^p}$

$\rm{NP} \subset \rm{P/poly} \quad \Rightarrow \quad \rm{AM}=\rm{MA}$

$\rm{coNP} \subset \rm{NP/poly} \quad \Rightarrow \quad \rm{PH}=\rm{\Sigma\_3^p}=\rm{\Pi\_3^p}$


---

### Answer by username_0 on 2010-12-08. Score: 5

Here is an example from Computational Complexity: A Modern Approach by Arora and Barak (page 128):

If every language in $EXP$ has circuits of size $o(2^{n} /n)$ then $P \ne NP$


---

### Answer by username_0 on 2010-11-25. Score: 5

I found a nice example in Dick Lipton's blog, [An Approach to P=NP via Descriptive Complexity](http://rjlipton.wordpress.com/2010/01/05/an-approach-to-pnp-via-descriptive-complexity/), He proposes an upper bound conjecture (Hypothesis H) that would imply $P\ne NP$.

> **Hypothesis H**: Suppose that $C$ are Horn clauses $C\_{1} \wedge \dots \wedge C\_{m}$. 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.
>
> **Theorem**: Suppose that Hypothesis H is true. Then, $P \ne NP$


---

