ALOGTIME and a conjecture of S.A. Cook (Extended Abstract)
Peter Clote · Logic in Computer Science · 1990
Using sequential, machine-independent characterizations of the parallel complexity classes ACk and NCk, we establish the following conjecture of S.A. Cook. There is a free variable equational logic ALV with the property that if f,g are function symbols for ALOGTIME computable functions for which ‘ f = g’ is provable in ALV, then there are polynomial size Frege proofs for the infinite family {If = : n, m E