On quasilinear-time complexity theory
From MaRDI portal
Publication:672330
DOI10.1016/0304-3975(95)00031-QzbMath0873.68070OpenAlexW2030312085WikidataQ56018874 ScholiaQ56018874MaRDI QIDQ672330
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
Related Items (8)
Amplifying circuit lower bounds against polynomial time, with applications ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ Algorithmic theory of free solvable groups: randomized computations. ⋮ Observations on complete sets between linear time and polynomial time ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}
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
This page was built for publication: On quasilinear-time complexity theory
