Circuit Lower Bounds à la Kolmogorov
| Autor: | Sophie Laplante, Lance Fortnow |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Discrete mathematics
Lemma (mathematics) Computational complexity theory Computation Probabilistic logic TheoryofComputation_GENERAL Combinatorial proof Upper and lower bounds Computer Science Applications Theoretical Computer Science Combinatorics Computational Theory and Mathematics Boolean function Randomness Information Systems Mathematics |
| Zdroj: | Information and Computation. 123:121-126 |
| ISSN: | 0890-5401 |
| DOI: | 10.1006/inco.1995.1161 |
| Popis: | In a recent paper, Razborov ( in "Feasible Mathematics II" (P. Clote and J. Remmel, Eds.), gave a new combinatorial proof of Hastad′s switching lemma ( in "Randomness and Computation" (S. Micali, Ed.), pp. 143-170, 1989) eliminating the probabilistic argument altogether. In this paper we adapt his proof and propose a Kolmogorov complexity-style switching lemma, from which we derive the probabilistic switching lemma as well as a Kolmogorov complexity-style proof of circuit lower bounds for parity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect