Logic in Computer Science (LICS 1990)

Paper: ALOGTIME and a conjecture of S.A. Cook (at LICS 1990)

Authors: Clote, P.

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

BibTeX

  @InProceedings{Clote-ALOGTIMEandaconject,
    author = 	 {Clote, P.},
    title = 	 {ALOGTIME and a conjecture of S.A. Cook},
    booktitle =  {Proceedings of the Fifth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1990},
    year =	 1990,
    editor =	 {John Mitchell},
    month =	 {June}, 
    pages =      {181--189},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }