Time-space lower bounds for satisfiability and related problems on randomized machines.

摘要

Computational complexity studies the resources required for computers to solve certain problems; deciding satisfiability of Boolean formulas is one of the most fundamental such problems. This thesis proves lower bounds on the time and memory space required to solve satisfiability and related problems on randomized machines.;We establish the first randomized time-space lower bounds for the problem Sigma ℓSAT of deciding the validity of quantified Boolean formulas with at most ℓ-1 quantifier alternations. We show that for any integer ℓ ≥ 2 and constant c ℓ, there exists a positive constant d such that SigmaℓSAT cannot be computed by randomized machines with two-sided error in time nc and space nd. This result also applies to other natural complete problems in the polynomial-time hierarchy, such as maximizing the number of literals that can be removed from a disjunctive normal form formula without changing its meaning.;As for ℓ = 1, we argue that similar results for satisfiability or tautologies would follow from a simulation that swaps Arthur and Merlin in two-round Merlin-Arthur games at subquadratic cost. We prove that the latter requires non-black-box techniques: any Arthur-Merlin game requires time O( t2) to black-box simulate Merlin-Arthur games running in time t. This proves that known simulations of the latter class by the former with quadratic overhead are tight within the black-box setting.;In the case of the tautologies problem, we obtain nontrivial time-space lower bounds for randomized machines with one-sided error , i.e., randomized machines that can only err on tautological formulas. In fact, we prove new results for nondeterministic machines solving tautologies, which relates to proof complexity and the NP versus coNP problem: for every c 34 ≈ 1.587 there exists a positive d such that tautologies cannot be decided by nondeterministic machines in time nc and space nd.;We can do better in the one-sided error setting: we prove that for every constant c 2 cos(pi/7) ≈ 1.801, there exists a positive constant d such that tautologies cannot be decided by randomized machines with one-sided error in time nc and space nd.