On O(Tlog T) reduction from RAM computations to satisfiability

DOI10.1016/0304-3975(91)90177-4MaRDI QIDQ758197zbMATH OpenOpenAlexFDO

Authors John Michael Robson

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90177-4

zbMATH Keywords

reductionsatisfiabilityrandom access machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Lower bounds for RAMs and quantifier elimination
• A time lower bound for satisfiability
• Automata, Languages and Programming
• Time-space lower bounds for satisfiability
• Time-space lower bounds for satisfiability
• Time-space tradeoffs for satisfiability
• Mathematical Foundations of Computer Science 2005
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• Parameterized and subexponential-time complexity of satisfiability problems and applications

Cites work

• scientific article; zbMATH DE number 3978379 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Short propositional formulas represent nondeterministic computations
• Sorting in \(c \log n\) parallel steps

Cited in

(12)

• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Experiments with reduction finding
• Local reduction
• Nonuniform ACC circuit lower bounds
• Analysis of a new reduction calculus for the satisfiability problem
• Sorting, linear time and the satisfiability problem
• Shorter arithmetization of nondeterministic computations
• On quasilinear-time complexity theory
• Time-space tradeoffs for SAT on nonuniform machines
• Smoothing the Gap Between NP and ER
• Time-space tradeoffs for satisfiability
• Local reductions

This page was built for publication: On O(Tlog T) reduction from RAM computations to satisfiability

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