Technical Report CS0849

TR#:CS0849
Class:CS
Title: LOGICS CAPTURING RELATIVIZED COMPLEXITY CLASSES UNIFORMLY.
Authors: J.A. Makowsky and Y.B. Pnueli
PDFCS0849.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}.
CopyrightThe 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.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin