A medley for computational complexity: With applications of information theory, learning theory, and Ketan Mulmuley's parametric complexity technique
B.S. Loff Barreto · 2014
This thesis contains four parts. Each part studies a topic within computational complexity by applying techniques from other fields in theoretical computer science. In Chapter 1 we will use Kolmogorov complexity to study probabilistic polynomial-time algorithms. Let R denote the set of Kolmogorov-random strings, which are those strings x whose Kolmogorov complexity K(x) is at least as large as their length |x|. There are two main results. First, we show that any bounded-error probabilistic polynomial-time algorithm can be simulated by a deterministic polynomial-time algorithm that is allowed to make non-adaptive queries to R. Second, we show that for a time-bounded analogue of R (defined using time-bounded Kolmogorov complexity), it holds that any polynomial-time algorithm that makes non-adaptive queries to R can be simulated both in polynomial space and by circuits of polynomial size. This indicates that we are near to an alternative characterization of probabilistic polynomial-time as being exactly deterministic polynomial-time with non-adaptive queries to R. Such characterizations ultimately aim at using techniques from Kolmogorov complexity and computability to study the relationship between different complexity classes. As can be expected, the proofs in this chapter make essential use of such techniques. In Chapter 2 we make an effort at extending Mahaney’s theorem [74] to more general reductions, or — seen another way — strengthening the KarpLipton theorem [64] to a stronger collapse of the polynomial-time hierarchy. Mahaney’s theorem states that if Sat is m-reducible to a sparse set, then P = NP, and the Karp-Lipton theorem (more precisely, the strengthened version of Cai [40]) says that if Sat is Turing-reducible to a sparse set, then PH ⊆ ZPP. We prove that if a class of functions C has a polynomial-time learning algorithm in Angluin’s bounded error learning model, then if Sat is m-reducible to C, it follows that PH ⊆ P. Then from the existence of such an algorithm for linear-threshold functions, we conclude that if Sat is m-reducible to a linear-threshold function, then PH ⊆ P. It will be seen that both disjunctive and majority truth-table (non-adaptive) reductions to sparse sets are a special case of m-reductions to linear-threshold functions, and hence our results hold also for these kinds of