A time lower bound for satisfiability

DOI10.1007/978-3-540-27836-8_81MaRDI QIDQ5466530zbMATH OpenOpenAlexFDO

Authors Dieter Van Melkebeek, Ran Raz

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

zbMATH Keywords

computational complexityconondeterministic machinesdeterministic Turing machinelower boundssatisfiability

Mathematics Subject Classification ID

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

Recommendations

• A time lower bound for satisfiability
• 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.

Cited in

(16)

• Simultaneous (poly-time, log-space) lower bounds
• A time lower bound for satisfiability
• Time-space lower bounds for satisfiability
• scientific article; zbMATH DE number 5914170 (Why is no real title available?)
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Time-space lower bounds for satisfiability
• Deterministic versus nondeterministic time and lower bound problems
• A survey of lower bounds for satisfiability and related problems.
• scientific article; zbMATH DE number 4049049 (Why is no real title available?)
• Average time complexity of the SAT1. 2 algorithm
• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• On lower bounds for the time of computation
• One-tape Turing machine and branching program lower bounds for MCSP
• One-tape Turing machine and branching program lower bounds for MCSP
• On O(Tlog T) reduction from RAM computations to satisfiability

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 Q5466530)