On quasilinear-time complexity theory
From MaRDI portal
Publication:672330
DOI10.1016/0304-3975(95)00031-QzbMath0873.68070WikidataQ56018874 ScholiaQ56018874MaRDI QIDQ672330
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relativized isomorphisms of NP-complete sets
- On O(Tlog T) reduction from RAM computations to satisfiability
- Robust algorithms: a different approach to oracles
- Relativized circuit complexity
- NP is as easy as detecting unique solutions
- On helping by robust oracle machines
- Polynomial terse sets
- The complexity of optimization problems
- Bounded query classes and the difference hierarchy
- Some observations on the probabilistic algorithms and NP-hard problems
- On truth-table reducibility to SAT
- Bounded queries to SAT and the Boolean hierarchy
- Processor-efficient exponentiation in finite fields
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Universal classes of hash functions
- A taxonomy of complexity classes of functions
- Terse, superterse, and verbose sets
- Time bounded random access machines
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Classes of bounded nondeterminism
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- PP is as Hard as the Polynomial-Time Hierarchy
- A taxonomy of problems with fast parallel algorithms
- Natural Self-Reducible Sets
- Absolute results concerning one-way functions and their applications
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Probabilistic Algorithms in Finite Fields
- Linear time transformations between combinatorial problems
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Fast decoding of codes from algebraic plane curves
- A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate
- Relativization of questions about log space computability
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Satisfiability Is Quasilinear Complete in NQL
- Rudimentary Predicates and Relative Computation
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Relations Among Complexity Measures
- Nondeterminism within $P^ * $
- Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
- Randomness-optimal unique element isolation, with applications to perfect matching and related problems
- Two-Tape Simulation of Multitape Turing Machines
- Power indices and easier hard problems