Time-space lower bounds for satisfiability

MaRDI QIDQ2729236zbMATH OpenFDO

Authors Dieter Van Melkebeek

Publication date 18 July 2001

Published in Bulletin of the European Association for Theoretical Computer Science EATCS (Search for Journal in Brave)

zbMATH Keywords

random-access machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cited in

(14)

• Simultaneous (poly-time, log-space) lower bounds
• Time-space tradeoffs for satisfiability
• Conditional lower bounds for space/time tradeoffs
• A time lower bound for satisfiability
• scientific article; zbMATH DE number 6482141 (Why is no real title available?)
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Time-space lower bounds for satisfiability
• A survey of lower bounds for satisfiability and related problems.
• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Automata, Languages and Programming
• Automata, Languages and Programming
• Time-space tradeoffs for SAT on nonuniform machines
• On O(Tlog T) reduction from RAM computations to satisfiability

This page was built for publication: Time-space lower bounds for satisfiability

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