مرکز منطقه ای اطلاع رساني علوم و فناوري

DocumentCode :

2717063

Title :

ALOGTIME and a conjecture of S.A. Cook

Author :

Clote, Peter

fYear :

1990

fDate :

4-7 Jun 1990

Firstpage :

181

Lastpage :

189

Abstract :

Using sequential, machine-independent characterizations of the parallel complexity classes AC^k and NC^k, the author establishes a conjecture of S.A. Cook (1975) regarding polynomial size Frege proofs for a certain infinite family. A related result is established with constant formula-depth polynomial size Frege proofs for a system AV related to uniform AC⁰ functions

Keywords :

computational complexity; formal logic; theorem proving; ALOGTIME; infinite family; machine-independent characterizations; parallel complexity classes; polynomial size Frege proofs; sequential; Equations; Erbium; Logic; Polynomials;

fLanguage :

English

Publisher :

ieee

Conference_Titel :

Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e

Conference_Location :

Philadelphia, PA

Print_ISBN :

0-8186-2073-0

Type :

conf

DOI :

10.1109/LICS.1990.113744

Filename :

113744

Link To Document :

https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2717063