Time-space tradeoffs for satisfiability

DOI10.1006/jcss.1999.1671zbMath0955.68052OpenAlexW2015895898MaRDI QIDQ1567402

Lance J. Fortnow

Publication date: 18 February 2001

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1999.1671

zbMATH Keywords

satisfiabilitybranching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ On the approximability of clique and related maximization problems ⋮ Amplifying circuit lower bounds against polynomial time, with applications ⋮ An Improved Time-Space Lower Bound for Tautologies ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Robust simulations and significant separations ⋮ The minimum oracle circuit size problem ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ On the finite axiomatizability of ⋮ An improved time-space lower bound for tautologies ⋮ A theory for Log-Space and NLIN versus co-NLIN ⋮ Unnamed Item ⋮ Computing (and Life) Is All about Tradeoffs ⋮ A time lower bound for satisfiability ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativized isomorphisms of NP-complete sets
• On O(Tlog T) reduction from RAM computations to satisfiability
• Two time-space tradeoffs for element distinctness
• Short propositional formulas represent nondeterministic computations
• The problem of space invariance for sequential machines
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Relationships between nondeterministic and deterministic tape complexities
• Theory of Formal Systems. (AM-47)
• A time-space tradeoff for language recognition
• Towards separating nondeterminism from determinism
• PP is as Hard as the Polynomial-Time Hierarchy
• Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
• Alternation
• Satisfiability Is Quasilinear Complete in NQL
• Rudimentary Predicates and Relative Computation
• Relations Among Complexity Measures
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• On the Computational Complexity of Algorithms
• Two-Tape Simulation of Multitape Turing Machines
• The complexity of theorem-proving procedures
• Natural proofs