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

• 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

• A hierarchy for nondeterministic time complexity
• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3353257 (Why is no real title available?)
• 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

(17)

• Simultaneous (poly-time, log-space) lower bounds
• Local reduction
• Time-space lower bounds for satisfiability
• scientific article; zbMATH DE number 5914170 (Why is no real title available?)
• Local reductions
• 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 1555929 (Why is no real title available?)
• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• On lower bounds for the time of computation
• Limits on alternation trading proofs for time-space lower bounds
• An Improved Time-Space Lower Bound for Tautologies
• Automata, Languages and Programming
• Towards stronger depth lower bounds
• Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
• 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 Q2581273)