On O(Tlog T) reduction from RAM computations to satisfiability
From MaRDI portal
Publication:758197
DOI10.1016/0304-3975(91)90177-4zbMATH Open0724.68034OpenAlexW1969514863MaRDI QIDQ758197FDOQ758197
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
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
Analysis of algorithms and problem complexity (68Q25) Other degrees and reducibilities in computability and recursion theory (03D30)
Cites Work
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)
