Skip to content

A Problem With Proving Problems Are Hard

March 31, 2010
tags: , , , , , , ,


Kannan’s famous theorem on boolean circuits and the polynomial hierarchy

Dick Karp is to blame. Without him we would not have the annoying P=NP question, without him we would not have thousands of problems all appearing to be hard to solve, without him modern computational complexity would be completely different.

Just to be clear—in case my words do not come across properly—we owe Dick a great debt. Without his work, his leadership, his brilliant insights, the field would be very different, and we owe him a great deal of thanks. Thanks Dick.

Today I will talk about an ancient result of Ravi Kannan proved in 1982, a beautiful result, yet still one of the few known general circuit lower bounds. There have been some other results proved since then, but Ravi’s result is a landmark. This result is related to a result of Karp and myself: Dick and I proved KL:

Theorem: If SAT has polynomial size circuits, then the polynomial time hierarchy (PH) collapses to {\Sigma_2}.

This has been used both as a theorem and as a research direction over the years. A beautiful result, due to Jin-Yi Cai, is the huge improvement of this result to {S_{2}^{p}}. I will discuss this result another time.

One key application of the KL theorem is in the proof of the beautiful result of Ravi Kannan. I will discuss how to try and avoid using our theorem—what am I thinking?—to prove his theorem.

Kannan’s Theorem

A modern statement of Ravi’s theorem uses {\mathsf{SIZE}(n^{k})}: this is the complexity class of sets {S} so that for each length {n},

\displaystyle C(S_{n}(x)) \le n^{k}

where {C(S_{n})} is the boolean complexity of the function

\displaystyle S_{n}(x) = 1 \textrm{ if and only if } x \in S.

Theorem: For any {k > 1}, there is a set {S} in {\Sigma_{2}} so

\displaystyle S \not\in \mathsf{SIZE}(n^{k}).

Yes, Ravi actually proves more—{\Sigma_{2} \cap \Pi_{2}}—but all my comments will apply to the stronger theorem, so I will only discuss {\Sigma_{2}} in detail here.

Kannan’s Proof

Ravi’s first shows there is a language {L} in {\Sigma_{4}} such that

\displaystyle C(L_{n}) \ge n^{k}

for all {n}. He then uses KL in the following manner:

  1. The language SAT has polynomial size circuits: then by KL, PH hierarchy collapses to {\Sigma_{2}} and therefore {L} is in {\Sigma_{2}}. Thus, in this case his theorem is true.
  2. The language SAT has super-polynomial circuits: in this case his theorem is also true. Note, SAT is in NP = {\Sigma_{1} \subseteq \Sigma_{2}}.

Very neat. I pointed out once the great John Littlewood used a similar trick to prove a result in number theory:

  1. If the Riemann Hypothesis is true, then primes behave well and his theorem is true.
  2. If the Riemann Hypothesis is false, then primes behave poorly and his theorem is true.

So Ravi is in good company.

Kannan’s Proof—Can We Do Better?

There is an interesting issue with Ravi’s proof of his theorem—it is non-constructive and only shows there is a language with large circuits for infinitely many lengths {n}. Let’s look at the proof again. The language {L} is in {\Sigma_{4}} and

\displaystyle C(S_{n}) \ge n^{k}

is true for all {n}. Suppose that SAT is in {\mathsf{SIZE}(n^{k})}. Then, the PH hierarchy collapses to {\Sigma_{2}}. Thus, {L} is in {\Sigma_{2}} and we are done.

However, suppose SAT is not in {\mathsf{SIZE}(n^{k})}. Then, we only know that for an infinite number of lengths {n},

\displaystyle C(S_{n}) \ge n^{k}.

So Ravi’s proof does not show the existence of the language for all {n}. It only shows the existence for {n} infinitely often.

I would like to construct an explicit language {L} in {\Sigma_{2}} so

\displaystyle C(S_{n}) \ge n^{k}

for all {n}. I cannot—yet. I have been working with Ken Regan on an approach, but it does not work.

How To Compare Circuits Fast

One reason Ravi needs {\Sigma_{4}} is he needs to compare circuits to see if they are equivalent. Various others have since improved this step, getting {\Sigma_3 \cap \Pi_3} with hardness for all {n}, or {\Sigma_2} with hardness for infinitely-many {n}, but still short of what we would like. The following idea attempts to meld these improvements, and though it is basically known and gets only the {\Sigma_3 \cap \Pi_3} result, perhaps it can be useful.

In any event it is a “trick” you may be able to use in other proofs, or to solve other problems. Many years ago I told this trick to Avi Wigderson—in the context of Kannan’s Theorem—and he said immediately to me:

How else could Ravi’s proof go?

Well Ravi’s proof does not use these ideas: obviously Avi figured out Kannan’s proof on his own. Oh well.

Let {A \equiv B} denote the two circuits {A} and {B} compute the same boolean function. Say a circuit with {x_{1},\dots,x_{n}} inputs is a {(m,n)}-circuit provided only the inputs {x_{1},\dots,x_{m}} are used in any gate. The rest of the inputs are never used in a gate, and so have no effect on the output of the circuit. The key points of {(m,n)}-circuits are the following lemmas:

Lemma: Let {A} and {B} be {(m,n)}-circuits. Then, there is an algorithm to check if {A \equiv B} in time polynomial in {n} and {2^{m}}.

Proof: Clearly, we need only check the {2^{m}} inputs used by the circuits to determine if they compute the same boolean function. \Box

Lemma: Let {A} be a {(m,n)}-circuit, and let {B} be a circuit on {n} inputs. If {A \equiv B}, then there is a {B^{*}} {(m,n)}-circuit so {B \equiv B^{*}}, and

\displaystyle C(B^{*}) \le C(B).

Proof: Let {B^{*}} be the circuit {B} with {n-m} additional inputs

\displaystyle x_{m+1},\dots,x_{n}

set to {0}. It is easy to see {A} and {B^{*}} are equivalent. Also the complexity of {B^{*}} cannot go up after setting variables to {0}. \Box

If we go over Ravi’s proof and only consider {(m,n)}-circuits with {m = ck\log n}, then equality will be checkable in polynomial time, thus saving an alternation. This will also avoid a technical lemma Ravi needs: he had to prove a special version of the classic Claude Shannon theorem that most boolean functions have exponential complexity. Note, we can use the original theorem on {m} variables.

One could view the restriction to {(m,n)}-circuits as a “padding” trick, which helps us compare circuits in polynomial time. This brings down the complexity of the whole operation to {\Sigma_3} instead of {\Sigma_4}. A similar method defines the complement of the language {L}, thus achieving {\Sigma_3 \cap \Pi_3}.

Open Problems

The main open problem I would like to see solved is the construction of hard boolean functions in weak complexity classes. Also, I would like to see a stronger form Ravi’s theorem which shows the existence of a language with large circuit complexity in {\Sigma_2} proved for all {n}—if this is possible.

from → P=NP, People, Proofs
5 Comments leave one →
  1. Kenneth W. Regan permalink
    March 31, 2010 1:24 pm

    Online versions of the two references for improved versions of Kannan’s Theorem are:

    Superpolynomial versus Subexponential Circuit Size in the Exponential Hierarchy.
    Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe.
    Computing and Combinatorics Conference 1999 (COCOON 99) ,
    Springer LNCS Vol: 1627, pages 210–220.
    PDF of TR version.

    On Proving Circuit Lower Bounds against the. Polynomial-Time Hierarchy: Positive and. Negative Results. . Jin-Yi Cai and Osamu Watanabe
    Computing and Combinatorics Conference 2003 (COCOON 03) ,
    Springer LNCS Vol: 2697, pages 202–211.
    PDF version.

    The former has a more-general scaling but achieves the almost-all-n result for Sigma_3 intersect Pi_3, while the latter has the Sigma_2 result for infinitely-many n hardness.

    Reply
  2. c michael green permalink
    September 22, 2010 12:37 am

    I am grateful for SIZE(n^k)proof byR Kannan. I am recursive ie not dealing with circuits insitu directly. I have found I could express Cooks example of a set of numbers to answer a sub set zero queston of elementary standing IFF I expressed the simple output as part of SIZE so that the k took on the number of terms/ Or the inferred number of gaps between the numbers constituting the set ie a bald connection with studying reln within a set or string of numbers. Merely by carrying this into a larger arena of discussion elsewhere I hope to show that it is actually impossible to avoid the idea that there IS a link with an extension
    atempting to define how the Graft policy does equate with what might be termed an
    ‘inhibitory property. A bit devastated to find that RT has a connection with this as well not here defined I am glad I have SIZE at hand for the modelling in some Review with the author V Deol. on the market over the status of some ‘polylog’difficulty I am convinced it is not true that he can just outlaw a polylog attitude as something without a modular reference and globally different property than P and its NP story. Itwill tie in with the Graft(N) .given more confirmation working with a Univ supervisor I hope. THANKYOU AGAIN for the basic proof of connectivity.

    Reply
  3. c michael green permalink
    September 22, 2010 1:12 am

    PPS Previous REPLY Status-wise Im not well known beyond a response from DrTillman of Journal of Topology 08/09 issues Hardly the P equals NP problem then. Boundaries with Conjectures is so fascinating an emerging history.

    Reply

Trackbacks

  1. Twin Primes Are Useful | Gödel's Lost Letter and P=NP
  2. Consistency and P=NP | Gödel's Lost Letter and P=NP

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading