Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws

• Autorzy: Stewart I.A.
• Języki publikacji: EN

Abstrakty

EN

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ+(1), is such that the class of problems accepted by these program schemes is exactly the class of recursively enumerable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively enumerable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ.We show that the class of problems accepted by the program schemes of NPSQ is the union of the classes of problems defined by the sentences of all vectorized Lindstr¨om logics formed using operators whose corresponding problems are recursively enumerable and closed under extensions, and, as a result, has a zero-one law. Moreover, we also show that this class of problems can be realized as the class of problems defined by the sentences of a particular vectorized Lindstr¨om logic. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogues to a number of inequalities and hypotheses from computational complexity theory involving (non-deterministic) complexity classes ranging from NP through to ELEMENTARY.

Słowa kluczowe

EN

program schemes; Descriptive Complexity; Lindström logics; zero-one laws

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 411--435
• Opis fizyczny: Bibliogr. 40 poz.

Twórcy

autor

Stewart I.A.

• Department of Computer Science, Durham University, Science Labs, South Road, Durham DH1 3LE, U.K.,

Bibliografia

• [1] S. Abiteboul, M.Y. Vardi and V. Vianu, Fixpoint logics, relational machines and computational complexity, Journal of the Association for Computing Machinery 44 (1997) 30-56.
• [2] S. Abiteboul and V. Vianu, Generic computation and its complexity, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, ACM Press (1991) 209-219.
• [3] S. Abiteboul and V. Vianu, Computing with first-order logic, Journal of Computer and System Sciences 50 (1995) 309-335.
• [4] N. Alechina and Y. Gurevich, Syntax vs semantics on finite structures, Lecture Notes in Computer Science Volume 1261, Springer-Verlag (1997) 14-33.
• [5] A.A. Arratia-Quesada, S.R. Chauhan and I.A. Stewart, Hierarchies in classes of program schemes, Journal of Logic and Computation 9 (1999) 915-957.
• [6] A. Blass, Y. Gurevich and S. Shelah, Choiceless polynomial time, Annals of Pure and Applied Logic 100 (1999) 141-187.
• [7] B. Bollobás, Random Graphs, Academic Press (1985).
• [8] S. Brown, D. Gries and T. Szymanski, Universality of data retrieval languages, Proceedings of 6th Annual ACM Symposium on Principles of Programming Languages, ACM Press (1979) 110-117.
• [9] R. Constable and D. Gries, On classes of program schemata, SIAM Journal of Computing 1 (1972) 66-118.
• [10] E. Dahlhaus, Reduction to NP-complete problems by interpretations, Lecture Notes in Computer Science Volume 171, Springer-Verlag (1984) 357-365.
• [11] A. Dawar, Generalized quantifiers and logical reducibilities, Journal of Logic and Computation 5 (1995) 213-226.
• [12] A. Dawar, A restricted second-order logic for finite structures, Information and Computation 143 (1998) 154-174.
• [13] A. Dawar and E. Grädel, Generalized quantifiers and 0-1 laws, Proceedings of the 10th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press (1995) 54-64.
• [14] H.D. Ebbinghaus and J. Flum, Finite Model Theory, Springer-Verlag (1995).
• [15] R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computation (ed. R.M. Karp), Volume 7 of SIAM-AMS Proceedings (1974) 43-73.
• [16] H. Friedman, Algorithmic procedures, generalized Turing algorithms and elemenatry recursion theory, in: Logic Colloquium 1969 (ed. R.O. Gandy and C.M.E. Yates), North-Holland (1971) 361-390.
• [17] M.R. Garey, A catalog of complexity classes, in: Handbook of Theoretical Computer Science Volume A (ed. J. van Leeuwen), Elsevier (1990) 67-161.
• [18] R.L. Gault and I.A. Stewart, An infinite hierarchy in a class of polynomial-time program schemes, Theory of Computing Systems 39 (2006) 753-783.
• [19] G. Gottlob, Relativized logspace and generalized quantifiers over finite ordered structures, Journal of Symbolic Logic 62 (1997) 545-574.
• [20] E. Grädel, P.G. Kolaitis, L. Libkin, M. Marx, J. Spencerand M.Y. Vardi, S. WeinsteinFinite-model Theory and Its Applications, Springer (2003).
• [21] M. Grohe, Existential least fixed-point logic and its relatives, Journal of Logic and Computation 7 (1997) 205-228.
• [22] Y. Gurevich, Logic and the challenge of computer science, in: Current Trends in Theoretical Computer Science (ed. E. Bőrger), Computer Science Press (1988) 1-57.
• [23] Y. Gurevich, Evolving algebras 1993: Lipari guide, in: Specification and Validation (ed. E. Bőrger), Oxford University Press (1995) 9-36.
• [24] D. Harel and D. Peleg, On static logics, dynamic logics, and complexity classes, Information and Control 60 (1984) 86-102.
• [25] N. Immerman, Relational queries computable in polynonial time, Information and Control 68 (1986) 86-104.
• [26] N. Immerman, Languages that capture complexity classes, SIAM Journal of Computing 16 (1987) 760-778.
• [27] N. Immerman, Descriptive Complexity, Springer-Verlag (1998).
• [28] N.D. Jones and S.S. Muchnik, Even simple programs are hard to analyse, Journal of the Association for Computing Machinery 24 (1972) 338-350.
• [29] C. Lautemann, T. Schwentick and I.A. Stewart, Positive versions of polynomial time, Information and Computation 147 (1998) 145-170.
• [30] D. Leivant, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences 39 (1989) 51-83.
• [31] L. Libkin, Elements of Finite Model Theory, Springer (2004).
• [32] M. Otto, Bounded Variable Logics and Counting, Lecture Notes in Logic Volume 9, Springer-Verlag (1997).
• [33] M. Paterson and N. Hewitt, Comparative schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation, ACM Press (1970) 119-128.
• [34] I.A. Stewart, Logical and schematic characterization of complexity classes, Acta Informatica 30 (1993) 61-87.
• [35] I.A. Stewart, Logical description of monotone NP problems, Journal of Logic and Computation 4 (1994) 337-357.
• [36] I.A. Stewart, Program schemes, arrays, Lindstrőm quantifiers and zero-one laws, Theoretical Computer Science 275 (2002) 283-310.
• [37] I.A. Stewart, Using program schemes to logically capture polynomial-time on certain classes of structures, London Mathematical Society Journal of Computation and Mathematics 6 (2003) 40-67.
• [38] I.A. Stewart, Logical and complexity-theoretic aspects of models of computation with restricted access to arrays, Journal of Logic and Computation, to appear.
• [39] J. Tiuryn and P. Urzyczyn, Some relationships between logics of programs and complexity theory, Theoretical Computer Science 60 (1988) 83-108.
• [40] M. Vardi, Complexity of relational query languages, Proceedings of 14th Annual ACM Symposium on Theory of Computing, ACM Press (1982) 137-146.