The recursion-theoretic structure of complexity classes (Q1064320): Difference between revisions

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.