# Technical Report CS0849

 TR#: CS0849 Class: CS Title: LOGICS CAPTURING RELATIVIZED COMPLEXITY CLASSES UNIFORMLY. Authors: J.A. Makowsky and Y.B. Pnueli PDF CS0849.pdf Abstract: We introduce the notion of a logic capturing a relativized complexity class uniformly by treating both generalized quantifiers and oracles as indeterminates and requiring that the correspondence be uniform. Besides reinterpreting previous results from this point of view, we show that Fixed Point Logic with inflationary fixed points {\em IFPL} captures {\bf P} uniformly, whereas First Order Logic {\em FOL}$[K_1,...,K_m]$ with any number of generalized quantifiers cannot capture uniformly a relativized complexity class which contains $NC_2$. This contrasts the fact that in the non-uniform approach both {\em IFPL} and {\em FOL[ATC]} capture {\bf P}. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0849), rather than to the URL of the PDF files directly. The latter URLs may change without notice.