Limits on alternation trading proofs for time-space lower bounds (Q496301): Difference between revisions

This paper continues the thread from [the second author, LIPICS -- Leibniz Int. Proc. Inform. 5, 669--680 (2010; Zbl 1230.68187)] exploring tradeoffs between time complexity and quantifier alternation. Let \(\mathrm{DTISP}(t(n),s(n))\) be the class of queries deterministically computable in time \(t(n)\) and space \(s(n)\), and let \(\mathrm{DTS}(t(n))=\mathrm{DTISP}(t(n),n^{o(1)})\). In [the second author, Comput. Complexity 17, No. 2, 179--219 (2008; Zbl 1149.68034)], it was shown that if \(0<c<2\cos(2\pi/7)\), then Satisfiability is not RAM-computable in time \(n^c\) and space \(n^{o(1)}\); the proof entailed rules of inference consisting of inclusions of complexity classes, and by assuming that Satisfiability was so computable a contradiction was obtained. In [Zbl 1230.68187], a system of rules of inference based on tradeoffs between time complexity and quantifier alternation was introduced. These rules dealt with complexity classes of the form \(^a(Q_1n^x)^b\cdots(Q_m n^z)^d\) \(\mathrm{DTS}(n^w)\), with alternating quantifiers, where \(a,b,\dots,d\) bounded the amount of deterministic computation between blocks of existential or universal moves, each \(Q_i n^u\), \(Q_i \in \{ \forall, \exists\}\), represented a block of existential or universal moves, and \(\mathrm{DTS}(n^w)\) represented a computation within time bound \(n^w\). There were two kinds of rules: 1. Speedup. Reducing computational time by introducing an alternation. These rules were of the form \(\cdots\;{^a(Qn^x)}^b\mathrm{DTS}(n^w)\subseteq\cdots\;{^a(Qn^{x'})}^{b'}(\bar Qn^y)^b\mathrm{DTS}(n^{w'})\), where \(\bar Q\) is the dual of \(Q\), \(b'\geq b\), and \(w'<w\). (In this paper, \(y=0\), a fact not used in this paper.) 2. Slowdown. Eliminating an alternation at the price of increasing computation time. These rules were of the form \(\cdots \;{^a(Qn^x)}^b\mathrm{DTS}(n^w)\subseteq\cdots\;{^a\mathrm{DTS}}(n^{w'})\) where \(w'>w,b\). Using these rules, the assumption that Satisfiability is in \(\mathrm{DTS}(n^c)\) for \(c<2\cos(2\pi/7)\) leads to \(\mathrm{DTS}(n^b)\subseteq\mathrm{DTS}(n^c)\) for some \(b<c\), entailing a contradiction. This paper introduces a simplified system of rules, and then proves a variant of a conjecture from [Zbl 1230.68187]: using these simplified rules, it is not possible to prove that Satisfiability is not in \(\mathrm{DTS}(n^c)\) for \(c>2\cos(2\pi/7)\). This is the primary result of this paper: the rest of the paper consists of a finer analysis of the limits of a variant of this apparatus: using a computer search, the authors compute values of a monotonic decreasing function \(c=c(\epsilon)\) on \([0,1]\) such that this apparatus confirms that \(\mathrm{SAT}\not\in\mathrm{DTISP}(n^{c'},n^{\epsilon})\) for \(c'<c(\epsilon)\) but not for \(c(\epsilon)>c'\). The arguments in this paper are elementary but long and intricate and, in a sense, repetitive. (One consequence is that there are occasional leaps in the paper.) This suggests that a major simplification of the apparatus would not only be possible but would be enlightening.