On quasilinear-time complexity theory (Q672330): Difference between revisions

@@ Property / Wikidata QID @@
+Q56018874
@@ Property / Wikidata QID: Q56018874 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q4091421
@@ Property / cites work: Q4091421 / rank @@
+Normal rank
@@ Property / cites work @@
+Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
+Normal rank
@@ Property / cites work @@
+Polynomial terse sets
@@ Property / cites work: Polynomial terse sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q4206394
@@ Property / cites work: Q4206394 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4039803
@@ Property / cites work: Q4039803 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded queries to SAT and the Boolean hierarchy
@@ Property / cites work: Bounded queries to SAT and the Boolean hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
+Normal rank
@@ Property / cites work @@
+Bounded query classes and the difference hierarchy
+Normal rank
@@ Property / cites work @@
+Terse, superterse, and verbose sets
@@ Property / cites work: Terse, superterse, and verbose sets / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Nondeterminism within $P^ *  $
@@ Property / cites work: Nondeterminism within $P^ * $ / rank @@
+Normal rank
@@ Property / cites work @@
+On truth-table reducibility to SAT
@@ Property / cites work: On truth-table reducibility to SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Universal classes of hash functions
@@ Property / cites work: Universal classes of hash functions / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness-optimal unique element isolation, with applications to perfect matching and related problems
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+Time bounded random access machines
@@ Property / cites work: Time bounded random access machines / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time transformations between combinatorial problems
+Normal rank
@@ Property / cites work @@
+Classes of bounded nondeterminism
@@ Property / cites work: Classes of bounded nondeterminism / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativized isomorphisms of NP-complete sets
@@ Property / cites work: Relativized isomorphisms of NP-complete sets / rank @@
+Normal rank
@@ Property / cites work @@
+ON THE NOTION OF LINEAR TIME COMPUTABILITY
@@ Property / cites work: ON THE NOTION OF LINEAR TIME COMPUTABILITY / rank @@
+Normal rank
@@ Property / cites work @@
+Q3826533
@@ Property / cites work: Q3826533 / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Tape Simulation of Multitape Turing Machines
@@ Property / cites work: Two-Tape Simulation of Multitape Turing Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Q4281521
@@ Property / cites work: Q4281521 / rank @@
+Normal rank
@@ Property / cites work @@
+Absolute results concerning one-way functions and their applications
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast decoding of codes from algebraic plane curves
+Normal rank
@@ Property / cites work @@
+Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
+Normal rank
@@ Property / cites work @@
+Some observations on the probabilistic algorithms and NP-hard problems
+Normal rank
@@ Property / cites work @@
+On helping by robust oracle machines
@@ Property / cites work: On helping by robust oracle machines / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of optimization problems
@@ Property / cites work: The complexity of optimization problems / rank @@
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+Normal rank
@@ Property / cites work @@
+Q4023358
@@ Property / cites work: Q4023358 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4146667
@@ Property / cites work: Q4146667 / rank @@
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+Normal rank
@@ Property / cites work @@
+Q4743737
@@ Property / cites work: Q4743737 / rank @@
+Normal rank
@@ Property / cites work @@
+Relations Among Complexity Measures
@@ Property / cites work: Relations Among Complexity Measures / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic Algorithms in Finite Fields
@@ Property / cites work: Probabilistic Algorithms in Finite Fields / rank @@
+Normal rank
@@ Property / cites work @@
+On O(Tlog T) reduction from RAM computations to satisfiability
+Normal rank
@@ Property / cites work @@
+Satisfiability Is Quasilinear Complete in NQL
@@ Property / cites work: Satisfiability Is Quasilinear Complete in NQL / rank @@
+Normal rank
@@ Property / cites work @@
+Robust algorithms: a different approach to oracles
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Natural Self-Reducible Sets
@@ Property / cites work: Natural Self-Reducible Sets / rank @@
+Normal rank
@@ Property / cites work @@
+A taxonomy of complexity classes of functions
@@ Property / cites work: A taxonomy of complexity classes of functions / rank @@
+Normal rank
@@ Property / cites work @@
+A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate
+Normal rank
@@ Property / cites work @@
+Q4729350
@@ Property / cites work: Q4729350 / rank @@
+Normal rank
@@ Property / cites work @@
+Power indices and easier hard problems
@@ Property / cites work: Power indices and easier hard problems / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient checking of polynomials and proofs and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q4720786
@@ Property / cites work: Q4720786 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3997777
@@ Property / cites work: Q3997777 / rank @@
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385524
@@ Property / cites work: Q4385524 / rank @@
+Normal rank
@@ Property / cites work @@
+Processor-efficient exponentiation in finite fields
+Normal rank
@@ Property / cites work @@
+Q3707407
@@ Property / cites work: Q3707407 / rank @@
+Normal rank
@@ Property / cites work @@
+Relativized circuit complexity
@@ Property / cites work: Relativized circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Complete sets and the polynomial-time hierarchy
@@ Property / cites work: Complete sets and the polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Rudimentary Predicates and Relative Computation
@@ Property / cites work: Rudimentary Predicates and Relative Computation / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(95)00031-q
+Normal rank
@@ Property / OpenAlex ID @@
+W2030312085
@@ Property / OpenAlex ID: W2030312085 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:672330