Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines
verfasst von : Scott Diehl, Dieter van Melkebeek
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We establish the first polynomial-strength time-space lower bounds for problems in the linear-time hierarchy on randomized machines with bounded two-sided error. We show that for any integer ℓ > 1 and constant
c
< ℓ, there exists a positive constant
d
such that QSAT
ℓ
cannot be computed by such machines in time
n
c
and space
n
d
, where QSAT
ℓ
denotes the problem of deciding the validity of a Boolean first-order formula with at most ℓ–1 quantifier alternations. Corresponding to ℓ = 1, we prove that for any constant
c
<
φ
≈ 1.618, there exists a positive constant
d
such that the set of Boolean tautologies cannot be decided by a randomized machine with one-sided error in time
n
c
and space
n
d
.