On O(Tlog T) reduction from RAM computations to satisfiability
From MaRDI portal
Publication:758197
DOI10.1016/0304-3975(91)90177-4zbMath0724.68034OpenAlexW1969514863MaRDI QIDQ758197
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
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