A complexity theory based on infinitely often conditions (computation, turing, algorithms, hierarchies)
Andrea Roli · 1986
In this dissertation, we define a new model for complexity theory. By replacing the almost everywhere conditions of traditional complexity theory by infinitely often conditions, we define the IO-complexity. We define IO-complexity classes of bound f(n) with density function d(n). We identify the IO-classes with density 1 to the worst-case classes. We establish the foundations of the new complexity theory by extending the results of the worst-case complexity to the IO-complexity. We study time, space and density hierarchies of languages of deterministic and non-deterministic IO-complexity classes. These results when stated in terms of worst-case complexity are strengthenings of previous hierarchy results; they say that there is a language L computable in time g(n) but every machine for L exceeds time f(n) on every word of length n for infinitely many n. For space bounds, we show the existence of a language L computable in space g(n) such that every machine for L can operate within space f(n) only for a constant number of points. We show that there exists positive density function d(n) for which P(d(n)) (NOT=) NP(d(n)) if and only if P (NOT=) NP. On the other hand if there exists a positive density function d(n) for which P(d(n)) = NP(d(n)) then E = NE. We show that a recursive language L is in a IO-complexity class of bound f(n) with density d(n) if and only if L can be approximated by f(n) bounded machine agreeing with L on input w with probability at least d((VBAR)w(VBAR)). We also show the relationship between the IO-complexity classes and some non-standard complexity classes. We relate the mean-case, the median-case and the probabilistic complexity classes to IO-complexity classes with density functions. Finally, we point out open questions related to the IO-complexity.