Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines
Jerzy Tyszkiewicz ยท Fundamenta Informaticae ยท 1997
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+1 p level in the polynomial time hierarchy in terms of reflective relational machines which use either ฮ k 0 or ฮฃ k p queries.