The recursion-theoretic structure of complexity classes

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

Let A be any language. A is said to be a gap language if A is the union of the maximal subsets of A of the form \(\{\) \(w| m\leq | w| \leq n\}\) (m\(\leq n\in N)\) (intervals of A). The gaps of A are the intervals of \(\bar A.\) A class \({\mathbb{C}}\) of languages is said to be recursively gap closed if for every recursive gap language \(G_ 0\) with infinitely many gaps and intervals, there is a language \(G\in {\mathbb{C}}\) such that \(\bar G\in {\mathbb{C}}\) and \(G_ 0\) contains infinitely many intervals belonging to G as well as gaps belonging to \(\bar G.\) A class of sets \({\mathbb{C}}\) is recursively presentable if there is an effective sequence \(M_ i\) of total Turing machines such that \({\mathbb{C}}=\{L(M_ i)|\) \(i\in N\}.\) The author shos that if \({\mathbb{C}}\) is a class of recursive languages which is recursive gap closed and closed under union and intersection, and \({\mathbb{C}}_ 1\), \({\mathbb{C}}_ 2\) are recursively presentable classes which are closed under finite variations then \({\mathbb{C}}\subseteq {\mathbb{C}}_ 1\cup {\mathbb{C}}_ 2\Rightarrow {\mathbb{C}}\subseteq C_ 1\) or \({\mathbb{C}}\subseteq {\mathbb{C}}_ 2\); and \({\mathbb{C}}={\mathbb{C}}_ 1\cup {\mathbb{C}}_ 2\Rightarrow {\mathbb{C}}={\mathbb{C}}_ 1\) or \({\mathbb{C}}={\mathbb{C}}_ 2.\) The article contains a series of results closely related to the one just mentioned. The complexity classes DTIME(n), DSPACE\(_{on-line}(\log n)\), the class of context-sensitive languages are shown to be recursively gap closed. The class of context-free languages and hence also that of regular languages, is not recursively gap closed. The article contains a number of other results.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: The recursion-theoretic structure of complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1064320)