ALOGTIME and a conjecture of S.A. Cook
| Autor: | Peter Clote |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Discrete mathematics
Polynomial Conjecture Proof complexity Applied Mathematics Function (mathematics) Characterization (mathematics) Computer Science::Computational Complexity Descriptive complexity theory Propositional calculus Mathematical proof Propositional formula Combinatorics PH Computable function TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Artificial Intelligence TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Constant (mathematics) Variable (mathematics) Mathematics |
| Zdroj: | [1990] Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science. |
| Popis: | Usingsequential, machine-independent characterization of theparallel complexity classesAC k andNC k , we establish the following conjecture of S.A. Cook. There is a free variable equational logicALV with the property thatif f, g are function symbols forALOGTIME computable functions for which “f=g” is provable inALV, then there are polynomial size Frege proofs for the infinite family {|f=g| n :n, m∈ℕ} of propositional tautologies. Here, the propositional formula |f=g| expresses the equality off andg on inputs of length at mostn, provided that the function values are of length at mostm. We establish a related result with constant formula-depth polynomial size Frege proofs for a systemAV related to uniformAC 0 functions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|