<p>You can find another view of the "bait and switch" argument in the <a href="http://www.cs.princeton.edu/theory/complexity/naturalchap.pdf" rel="nofollow">natural proofs</a> chapter of Arora-Barak. They use the same argument to argue that a "formal complexity measure" style lower bound argument must apply to random functions with high probability. But if a formal complexity measure</p>

<ol>
<li>assigns high complexity to a random function </li>
<li>does not assign high complexity to an easy function</li>
<li>can be easily computed from the truth table of a function</li>
</ol>

<p>then it can be used to break pseudorandom generators. This is what the natural proofs barrier is, informally. We argued that 1. is very reasonable for many approaches to lower bounds, without 2. the complexity measure seems useless, and 3. is based on the observation that we have been able to turn most combinatorial existence proofs into efficient algorithms, and on the intuition that an inherently non-constructive proof is a hard one to devise. </p>

<p>You can make the above more concrete by coming up with very efficient pseudorandom generators. If a function can be computed inside a complexity $C$ that looks pseudorandom to functions from a class $C'$, then a measure computable inside $C'$ is doomed for lowerbounds against $C$. </p>

CC BY-SA 4.0
2020-05-16T19:47:56.607Z
Razborov Rudich only prove halfexp impossibility with these kind of techniques. This is far from quadratic. No?
Turbo
CC BY-SA 3.0
2013-05-29T03:19:21.460Z
2013-05-29T03:19:21.460Z
Sasho Nikolov
<p>Here is an explanation from Lipton's blog: <a href="http://rjlipton.wordpress.com/2009/02/12/bait-and-switch-why-lower-bounds-are-so-hard/">Bait and Switch: Why Are Lower Bounds so Hard?</a> </p>

<p>As Grochow observed, Rudich's insight applies equally well to $n^2$ lower bounds as to super-polynomial lower bounds. </p>

<p>Rudich's insight explains why any lower bound proof that it is based on the following method cannot work. </p>

<blockquote>
  <p>"any computation that computes $f$ must make slow progress toward $f$. Each computational step can only get you a little bit closer to the final goal, thus the computation will take many steps."</p>
</blockquote>

<p>Basically, there is no measure of progress that can survive the Bait and Switch trick of Rudich and successfully leads to a lower bound.  </p>

CC BY-SA 4.0
2020-05-16T19:49:39.137Z
A heuristic argument is far from a proof of difficulty of quadratic lower bound.
Turbo
CC BY-SA 3.0
2013-05-29T01:49:04.750Z
2013-05-29T03:01:17.340Z
2013-05-29T03:01:17.340Z
Mohammad Al-Turkistany
<p>This is a follow up to my previous question: </p>

<p><a href="https://cstheory.stackexchange.com/questions/17578">Best known deterministic time complexity lower bound for a natural problem in NP</a></p>

<p>I find it bewildering that we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem that people care about and try to design better algorithms for. Our Exponential Time Hypothesis conjecture states that SAT cannot be solved in subexponential deterministic time, yet we cannot even prove SAT (or any other interesting NP problem) requires quadratic time! </p>

<p>I know interesting is somewhat subjective and vague. I don't have a definition. But let me try to describe what I consider to be an interesting problem: 
I am talking about problems which more than a few people find interesting. I am not talking about isolated problems mainly designed to answer some theoretical question. If people are not trying to find faster algorithms for a problem then it is an indication that the problem is not that interesting.
If you want concrete examples of interesting problems consider the problems in Karp's 1972 paper or in Garey and Johnson 1979 (most of them). </p>

<blockquote>
  <p>Is there any explanation for why we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem?</p>
</blockquote>

CC BY-SA 3.0
2013-05-27T17:21:45.897Z
You could make the problem more concrete by specifying certain NP-complete problems. And if you don't know, you could try another question asking for examples of "interesting" in the sense of there being work on finding algorithms or building practical solvers.
Vijay D
CC BY-SA 3.0
2013-05-27T17:27:37.550Z
@VijayD, I will post that question, thanks for suggesting it.
Anonymous
CC BY-SA 3.0
2013-05-27T19:10:01.247Z
Because lower bounds are hard?  What sort of explanation would satisfy you?
Jeffε
CC BY-SA 3.0
2013-05-27T23:00:50.700Z
@JɛﬀE how about nontrivial explanations which are informative and insightful? Intuitions or results explaining why we are stuck where we are in proving lower bounds. Since our claims has been much stronger than our results I am sure other experts have thought about why after decades of trying we haven't been able to get a quadratic lower bound on an interesting NP problem.
Anonymous
CC BY-SA 3.0
2013-05-28T03:01:43.440Z
My explanation is that our current computation models and our tools are not built to deal with complexity questions. These models and tools were natural evolution from the ones used in computability theory and I believe that is why they fail to prove any non-trivial lower bound on any interesting natural problem in NP. We need completely new information theoretic tools and techniques.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-28T16:46:46.853Z
Here is an explanation from Lipton's blog; Bait and Switch: Why Are Lower Bounds so Hard? http://rjlipton.wordpress.com/2009/02/12/bait-and-switch-why-lower-bounds-are-so-hard/
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-28T18:37:58.030Z
@MohammadAl-Turkistany: I think Rudich's insight, as on Lipton's blog, could be an answer, not just a comment. Especially as this argument, unlike some others, applies equally well to $n^2$ lower bounds as to super-polynomial lower bounds.
Joshua Grochow
CC BY-SA 3.0
2013-05-30T10:22:09.740Z
The question of quadratic time lower bounds is relevant when you restrict the algorithms to have very little (e.g., polylog) space, or when you look at one-tape Turing machines (which have very restricted access to memory). But when memory is unrestricted, and memory access is unrestricted, the "real" question is whether there are super-linear time lower bounds for interesting NP problems, in any random-access computational model. (Grandjean proved some super-linear lower bounds for multitape Turing machines, but they rely on the structure of one-dimensional tapes.)
Ryan Williams
<cc.complexity-theory><lower-bounds><big-picture><barriers>
Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?
Anonymous
# Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?

(Asked by: username_0 on 2013-05-27)

This is a follow up to my previous question:

[Best known deterministic time complexity lower bound for a natural problem in NP](https://cstheory.stackexchange.com/questions/17578)

I find it bewildering that we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem that people care about and try to design better algorithms for. Our Exponential Time Hypothesis conjecture states that SAT cannot be solved in subexponential deterministic time, yet we cannot even prove SAT (or any other interesting NP problem) requires quadratic time!

I know interesting is somewhat subjective and vague. I don't have a definition. But let me try to describe what I consider to be an interesting problem:
I am talking about problems which more than a few people find interesting. I am not talking about isolated problems mainly designed to answer some theoretical question. If people are not trying to find faster algorithms for a problem then it is an indication that the problem is not that interesting.
If you want concrete examples of interesting problems consider the problems in Karp's 1972 paper or in Garey and Johnson 1979 (most of them).

> Is there any explanation for why we haven't been able to prove any quadratic deterministic time lower bound for any interesting NP problem?

**Tags:** cc.complexity-theory, lower-bounds, big-picture, barriers
> **Comments:**
> **username_1**: You could make the problem more concrete by specifying certain NP-complete problems. And if you don't know, you could try another question asking for examples of "interesting" in the sense of there being work on finding algorithms or building practical solvers.  
> **username_0**: @VijayD, I will post that question, thanks for suggesting it.  
> **username_2**: Because lower bounds are hard?  What sort of explanation would satisfy you?  
> **username_0**: @JɛﬀE how about nontrivial explanations which are informative and insightful? Intuitions or results explaining why we are stuck where we are in proving lower bounds. Since our claims has been much stronger than our results I am sure other experts have thought about why after decades of trying we haven't been able to get a quadratic lower bound on an interesting NP problem.  
> **username_3**: My explanation is that our current computation models and our tools are not built to deal with complexity questions. These models and tools were natural evolution from the ones used in computability theory and I believe that is why they fail to prove any non-trivial lower bound on any interesting natural problem in NP. We need completely new information theoretic tools and techniques.  
> **username_3**: Here is an explanation from Lipton's blog; Bait and Switch: Why Are Lower Bounds so Hard? http://rjlipton.wordpress.com/2009/02/12/bait-and-switch-why-lower-bounds-are-so-hard/  
> **username_4**: @MohammadAl-Turkistany: I think Rudich's insight, as on Lipton's blog, could be an answer, not just a comment. Especially as this argument, unlike some others, applies equally well to $n^2$ lower bounds as to super-polynomial lower bounds.  
> **username_5**: The question of quadratic time lower bounds is relevant when you restrict the algorithms to have very little (e.g., polylog) space, or when you look at one-tape Turing machines (which have very restricted access to memory). But when memory is unrestricted, and memory access is unrestricted, the "real" question is whether there are super-linear time lower bounds for interesting NP problems, in any random-access computational model. (Grandjean proved some super-linear lower bounds for multitape Turing machines, but they rely on the structure of one-dimensional tapes.)  

---

## 2 answers

### Answer by username_3 on 2013-05-29. Score: 5

Here is an explanation from Lipton's blog: [Bait and Switch: Why Are Lower Bounds so Hard?](http://rjlipton.wordpress.com/2009/02/12/bait-and-switch-why-lower-bounds-are-so-hard/)

As Grochow observed, Rudich's insight applies equally well to $n^2$ lower bounds as to super-polynomial lower bounds.

Rudich's insight explains why any lower bound proof that it is based on the following method cannot work.

> "any computation that computes $f$ must make slow progress toward $f$. Each computational step can only get you a little bit closer to the final goal, thus the computation will take many steps."

Basically, there is no measure of progress that can survive the Bait and Switch trick of Rudich and successfully leads to a lower bound.

> **Comments:**
> **username_7**: A heuristic argument is far from a proof of difficulty of quadratic lower bound.  

---

### Answer by username_6 on 2013-05-29. Score: 4

You can find another view of the "bait and switch" argument in the [natural proofs](http://www.cs.princeton.edu/theory/complexity/naturalchap.pdf) chapter of Arora-Barak. They use the same argument to argue that a "formal complexity measure" style lower bound argument must apply to random functions with high probability. But if a formal complexity measure

1. assigns high complexity to a random function
2. does not assign high complexity to an easy function
3. can be easily computed from the truth table of a function

then it can be used to break pseudorandom generators. This is what the natural proofs barrier is, informally. We argued that 1. is very reasonable for many approaches to lower bounds, without 2. the complexity measure seems useless, and 3. is based on the observation that we have been able to turn most combinatorial existence proofs into efficient algorithms, and on the intuition that an inherently non-constructive proof is a hard one to devise.

You can make the above more concrete by coming up with very efficient pseudorandom generators. If a function can be computed inside a complexity $C$ that looks pseudorandom to functions from a class $C'$, then a measure computable inside $C'$ is doomed for lowerbounds against $C$.

> **Comments:**
> **username_7**: Razborov Rudich only prove halfexp impossibility with these kind of techniques. This is far from quadratic. No?  

---

