On quasilinear-time complexity theory
From MaRDI portal
DOI10.1016/0304-3975(95)00031-QzbMATH Open0873.68070OpenAlexW2030312085WikidataQ56018874 ScholiaQ56018874MaRDI QIDQ672330FDOQ672330
Authors: Juan-Miguel Gracia 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00031-q
Recommendations
- The Complexity of Decision Versus Search
- With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
- Sharply bounded alternation and quasilinear time
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Bounded queries to SAT and the Boolean hierarchy
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of optimization problems
- On truth-table reducibility to SAT
- A taxonomy of complexity classes of functions
- Title not available (Why is that?)
- Universal classes of hash functions
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- A taxonomy of problems with fast parallel algorithms
- Relativization of questions about log space computability
- Title not available (Why is that?)
- Relations Among Complexity Measures
- Title not available (Why is that?)
- Title not available (Why is that?)
- Robust algorithms: a different approach to oracles
- On helping by robust oracle machines
- The polynomial-time hierarchy
- Title not available (Why is that?)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Relativized circuit complexity
- Title not available (Why is that?)
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- NP is as easy as detecting unique solutions
- Nondeterminism within $P^ * $
- Title not available (Why is that?)
- PP is as Hard as the Polynomial-Time Hierarchy
- Probabilistic Algorithms in Finite Fields
- Bounded queries to SAT and the Boolean hierarchy
- Title not available (Why is that?)
- Satisfiability Is Quasilinear Complete in NQL
- Two-Tape Simulation of Multitape Turing Machines
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Absolute results concerning one-way functions and their applications
- Title not available (Why is that?)
- Processor-efficient exponentiation in finite fields
- Complete sets and the polynomial-time hierarchy
- Time bounded random access machines
- Title not available (Why is that?)
- Classes of bounded nondeterminism
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- On O(Tlog T) reduction from RAM computations to satisfiability
- Linear time transformations between combinatorial problems
- Power indices and easier hard problems
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- Rudimentary Predicates and Relative Computation
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Terse, superterse, and verbose sets
- Polynomial terse sets
- Bounded query classes and the difference hierarchy
- Some observations on the probabilistic algorithms and NP-hard problems
- Natural Self-Reducible Sets
- Fast decoding of codes from algebraic plane curves
- A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate
- Title not available (Why is that?)
- Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Randomness-optimal unique element isolation, with applications to perfect matching and related problems
- Relativized isomorphisms of NP-complete sets
Cited In (10)
- Sharply bounded alternation and quasilinear time
- Algorithmic theory of free solvable groups: randomized computations.
- Hardness and hierarchy theorems for probabilistic quasi-polynomial time
- Is Valiant-Vazirani's isolation probability improvable?
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Observations on complete sets between linear time and polynomial time
- Amplifying circuit lower bounds against polynomial time, with applications
- Nonerasing, counting, and majority over the linear time hierarchy
- Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)
This page was built for publication: On quasilinear-time complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672330)
