11
$\begingroup$

This is a follow up to my previous question:

Best known deterministic time complexity lower bound for a natural problem in NP

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?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Because lower bounds are hard? What sort of explanation would satisfy you? $\endgroup$
    – Jeffε
    May 27, 2013 at 19:10
  • 3
    $\begingroup$ @JɛffE 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. $\endgroup$
    – Anonymous
    May 27, 2013 at 23:00
  • 3
    $\begingroup$ Here is an explanation from Lipton's blog; Bait and Switch: Why Are Lower Bounds so Hard? rjlipton.wordpress.com/2009/02/12/… $\endgroup$
    – Mohammad Al-Turkistany
    May 28, 2013 at 16:46
  • 3
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    May 28, 2013 at 18:37
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Ryan Williams
    May 30, 2013 at 10:22

2 Answers 2

Reset to default
5
$\begingroup$

Here is an explanation from Lipton's blog: Bait and Switch: Why Are Lower Bounds 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A heuristic argument is far from a proof of difficulty of quadratic lower bound. $\endgroup$
    – Turbo
    May 16, 2020 at 19:49
4
$\begingroup$

You can find another view of the "bait and switch" argument in the natural proofs 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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Razborov Rudich only prove halfexp impossibility with these kind of techniques. This is far from quadratic. No? $\endgroup$
    – Turbo
    May 16, 2020 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.