A time lower bound for satisfiability

DOI10.1016/J.TCS.2005.09.020zbMATH Open1090.68049OpenAlexW2034037257MaRDI QIDQ2581273FDOQ2581273

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

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.

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)

Cites Work

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

Cited In (15)

• Time-space lower bounds for satisfiability
• Automata, Languages and Programming
• Title not available (Why is that?)
• Simultaneous (poly-time, log-space) lower bounds
• Time-space lower bounds for satisfiability
• Local reduction
• Deterministic versus nondeterministic time and lower bound problems
• On lower bounds for the time of computation
• An Improved Time-Space Lower Bound for Tautologies
• Title not available (Why is that?)
• Limits on alternation trading proofs for time-space lower bounds
• On O(Tlog T) reduction from RAM computations to satisfiability
• Title not available (Why is that?)
• Local reductions
• A survey of lower bounds for satisfiability and related problems.

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)