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

DOI10.1016/0304-3975(91)90177-4zbMath0724.68034OpenAlexW1969514863MaRDI QIDQ758197

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)

Related Items

Local Reductions, Local reduction, Nonuniform ACC Circuit Lower Bounds, Smoothing the Gap Between NP and ER, Shorter arithmetization of nondeterministic computations, On quasilinear-time complexity theory, Time-space tradeoffs for SAT on nonuniform machines, Sorting, linear time and the satisfiability problem, Time-space tradeoffs for satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Short propositional formulas represent nondeterministic computations