Affiliations: Mathematische Grundlagen der Informatik, RWTH Aachen, Germany
Note: [] Author's current address: Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-057 Warsaw, Poland. E-mail jty@mimuw.edu.pl.
Abstract: We consider two kinds of reflective relational machines: the usual ones, which use first order queries, and existential reflective machines, which use only first order existential queries. We compare these two computation models. We build on already existing results for standard relational machines, obtained by Abiteboul, Pa-padimitriou and Vianu [2], so we prove only results for existential machines. First we show that for both standard and existential reflective machines the set of polynomial time computable Boolean queries consists precisely of all ๐ซ๐ฎ๐ซ๐๐โฐ computable queries. Then we go further and compare which classes of algorithms both kinds of machines represent. Unless ๐ซ๐ฎ๐ซ๐๐โฐ = ๐ซ๐ฉ๐ซ, there are ๐ซ๐ฎ๐ซ๐๐โฐ queries which cannot be computed by polynomial time existential reflective machines which use only polynomial amount of relational memory, while it is possible for standard reflective machines. We conclude that existential reflective machines, being equivalent in computational power to unrestricted machines, implement substantially worse algorithms than the latter. Concerning deciding ๐ซ classes of structures, every fixpoint query can be evaluated by a polynomial time unrestricted reflective machine using constant number of variables, while existential reflective machines need [n/2] variables to implement the graph connectivity query. So again the algorithms represented by existential reflective machines are worse. Finally, for each k we get a characterization of the ฮk+1p level in the polynomial time hierarchy in terms of reflective relational machines which use either ฮ k0 or ฮฃkp queries.
Keywords: Reflective relational machines, quality of algorithms, polynomial time, polynomial space, polynomial hierarchy
