Fundamenta Informaticae - Volume 91, issue 2

Authors: Stewart, Iain A.

Article Type: Research Article

Abstract: 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öm 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öm 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. Show more

Keywords: program schemes, descriptive complexity, Lindström logics, zero-one laws

DOI: 10.3233/FI-2009-0050

Citation: Fundamenta Informaticae, vol. 91, no. 2, pp. 411-435, 2009