Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines

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+1^p level in the polynomial time hierarchy in terms of reflective relational machines which use either Π_k⁰ or Σ_k^p queries.