Monotonous and randomized reductions to sparse sets
From MaRDI portal
Publication:4717050
DOI10.1051/ita/1996300201551zbMath0860.68051OpenAlexW2793345MaRDI QIDQ4717050
V. Arvind, Martin Mundhenk, Johannes Köbler
Publication date: 29 April 1997
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92530
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing functions with parallel queries to NP
- On random reductions from sparse sets to tally sets
- Some consequences of non-uniform conditions on uniform classes
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- On self-reducibility and weak P-selectivity
- NP is as easy as detecting unique solutions
- More complicated questions about maxima and minima, and some closures of NP
- Some observations on the probabilistic algorithms and NP-hard problems
- Reductions on NP and p-selective sets
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Turing machines with few accepting computations and low sets for PP
- On sparse hard sets for counting classes
- A comparison of polynomial time reducibilities
- On reductions of NP sets to sparse sets
- Relativizing relativized computations
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- On unique satisfiability and the threshold behavior of randomized reductions
- Self-reducibility
- A Note on Sparse Complete Sets
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Reducibilities on tally and sparse sets
- The complexity of promise problems with applications to public-key cryptography
- On Sets Truth-Table Reducible to Sparse Sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Relating Equivalence and Reducibility to Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- On the Computational Complexity of Small Descriptions
- SPARSE Reduces Conjunctively to TALLY
- Upper bounds for the complexity of sparse and tally descriptions
