Limits on alternation trading proofs for time-space lower bounds
type: Item
instance of: scholarly article
title: Limits on alternation trading proofs for time-space lower bounds
zbMATH Open document ID: 1338.68080
author: Samuel R. Buss
author: Ryan Williams
published in: Computational Complexity
publication date: 2015-09-21T00:00:00Z
review text: 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 \…
reviewed by: Gregory Loren McColm
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6483856
zbMATH Keywords: alternating quantifiers
zbMATH Keywords: alternating Turing machines
zbMATH Keywords: alternation
zbMATH Keywords: lower bounds
zbMATH Keywords: quantifier complexity
zbMATH Keywords: satisfiability
zbMATH Keywords: rules of inference
zbMATH Keywords: time-space tradeoffs
MaRDI profile type: Publication
full work available at URL: s00037-015-0104-9
OpenAlex ID: W2152166524
cites work: Algebrization
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
cites work: Time-space lower bounds for satisfiability
cites work: Towards separating nondeterminism from determinism
cites work: Inductive time-space lower bounds for SAT and related problems
cites work: Q4668733
cites work: A Survey of Lower Bounds for Satisfiability and Related Problems
cites work: A time lower bound for satisfiability
cites work: Q5628106
cites work: Natural proofs
cites work: Time-space tradeoffs for SAT on nonuniform machines
cites work: Lower Bounds for Quantum Communication Complexity
cites work: Time-space tradeoffs for counting NP solutions modulo integers
cites work: Q3113789
cites work: Alternation-Trading Proofs, Linear Programming, and Lower Bounds
Wikidata QID: Q113906246
DOI: 10.1007/S00037-015-0104-9
description: scientific article; zbMATH DE number 6483856