Uniform proofs of ACC representations
| Autor: | Samuel R. Buss |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
0209 industrial biotechnology Proofs of Fermat's little theorem Logic Boolean circuit 010102 general mathematics 02 engineering and technology Mathematical proof 01 natural sciences Combinatorics Philosophy TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 020901 industrial engineering & automation Closure (mathematics) Bounded function 0101 mathematics Special case Representation (mathematics) Constant (mathematics) Mathematics |
| Zdroj: | Archive for Mathematical Logic. 56:639-669 |
| ISSN: | 1432-0665 0933-5846 |
| Popis: | We give a uniform proof of the theorems of Yao and Beigel–Tarui representing ACC predicates as constant depth circuits with $$\hbox {MOD}_{m}$$ gates and a symmetric gate. The proof is based on a relativized, generalized form of Toda’s theorem expressed in terms of closure properties of formulas under bounded universal, existential and modular counting quantifiers. This allows the main proofs to be expressed in terms of formula classes instead of Boolean circuits. The uniform version of the Beigel–Tarui theorem is then obtained automatically via the Furst–Saxe–Sipser and Paris–Wilkie translations. As a special case, we obtain a uniform version of Razborov and Smolensky’s representation of $$\hbox {AC}^{0}[p]$$ circuits. The paper is partly expository, but is also motivated by the desire to recast Toda’s theorem, the Beigel–Tarui theorem, and their proofs into the language of bounded arithmetic. However, no knowledge of bounded arithmetic is needed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|