A time lower bound for satisfiability

DOI10.1016/j.tcs.2005.09.020zbMath1090.68049OpenAlexW2034037257MaRDI QIDQ2581273

Ran Raz, Dieter van Melkebeek

Publication date: 9 January 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.020

zbMATH Keywords

computational complexitylower boundssatisfiabilitydeterministic Turing machineconondeterministic machines

Mathematics Subject Classification ID

Related Items (1)

Limits on alternation trading proofs for time-space lower bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short propositional formulas represent nondeterministic computations
• Two tapes versus one for off-line Turing machines
• A hierarchy for nondeterministic time complexity
• Time-space tradeoffs for satisfiability
• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• Towards separating nondeterminism from determinism
• Separating Nondeterministic Time Complexity Classes
• Relations Between Time and Tape Complexities
• One-tape, off-line Turing machine computations

This page was built for publication: A time lower bound for satisfiability