A time lower bound for satisfiability

DOI10.1016/J.TCS.2005.09.020MaRDI QIDQ2581273zbMATH OpenOpenAlexFDO

Authors Dieter Van Melkebeek, Ran Raz

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

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Automata, Languages and Programming
• Time-space lower bounds for satisfiability
• scientific article; zbMATH DE number 2156275
• Time-space lower bounds for satisfiability
• A survey of lower bounds for satisfiability and related problems.

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3353257 (Why is no real title available?)
• A hierarchy for nondeterministic time complexity
• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• One-tape, off-line Turing machine computations
• Relations Between Time and Tape Complexities
• Separating Nondeterministic Time Complexity Classes
• Short propositional formulas represent nondeterministic computations
• Time-space lower bounds for satisfiability
• Time-space tradeoffs for satisfiability
• Towards separating nondeterminism from determinism
• Two tapes versus one for off-line Turing machines

Cited in

(15)

• A survey of lower bounds for satisfiability and related problems.
• Time-space lower bounds for satisfiability
• Automata, Languages and Programming
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• Simultaneous (poly-time, log-space) lower bounds
• Time-space lower bounds for satisfiability
• Local reduction
• On lower bounds for the time of computation
• Deterministic versus nondeterministic time and lower bound problems
• An Improved Time-Space Lower Bound for Tautologies
• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• Limits on alternation trading proofs for time-space lower bounds
• On O(Tlog T) reduction from RAM computations to satisfiability
• scientific article; zbMATH DE number 5914170 (Why is no real title available?)
• Local reductions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581273)