Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Circuit Complexity and P versus NP

Expand Messages
  • Lance
    In 1983, Michael Sipser suggested an approach to separating P and NP. One way to gain insight into polynomial time would be to study the expressive power of
    Message 1 of 1 , Sep 27, 2005
    • 0 Attachment
      In 1983, Michael Sipser suggested an approach to separating P and NP.
      One way to gain insight into polynomial time would be to study the expressive power of polynomial-sized circuits. Perhaps the P=?NP question will be settled by showing that some problem in NP does not have polynomial-sized circuits. Unfortunately, there are currently no known techniques for establishing significant lower bounds on circuit size for NP problems. The strongest results to date give linear lower bounds, and it does not seem likely that the ideas there can go much beyond that.
      Over the next few years, circuit complexity played a central role in theoretical computer science. In 1985, Yao showed parity required exponential-sized constant-depth circuits, greatly strengthening the bounds given by Furst, Saxe and Sipser. Håstad quickly followed with essentially tight bounds.

      Shortly after Razborov showed that the clique function requires large monotone circuits. If we could just handle those pesky NOT gates, then we would have proven P≠NP.

      Then Razborov (in Russian) and Smolensky showed strong lower bounds for computing the modp function using constant depth circuits with modq gates for distinct primes p and q. These great circuit results kept coming one after another. We could taste P≠NP.

      But then it stopped. We still saw many good circuit complexity papers and some beautiful connections between circuit complexity and communication complexity, derandomization and proof complexity. But the march of great circuit results toward P≠NP hit a wall after the 1987 Razborov-Smolensky papers. As far as we know today, NP still could have linear-sized circuits and NEXP could have polynomial-sized constant-depth circuits with Mod6 gates.

      Boppana and Sipser wrote a wonderful survey on these results in the Handbook of Theoretical Computer Science The survey remains surprisingly up to date.

      --
      Posted by Lance to Computational Complexity at 9/27/2005 05:57:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.