Monotonous and randomized reductions to sparse sets

DOI10.1051/ITA/1996300201551MaRDI QIDQ4717050zbMATH OpenOpenAlexFDO

Authors Vikraman 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

zbMATH Keywords

oracle machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1318517
• On the existence of hard sparse sets under weak reductions
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets

Cites work

• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• A comparison of polynomial time reducibilities
• A Note on Sparse Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• Computing functions with parallel queries to NP
• Distinguishing conjunctive and disjunctive reducibilities by sparse sets
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• scientific article; zbMATH DE number 1318517 (Why is no real title available?)
• scientific article; zbMATH DE number 512798 (Why is no real title available?)
• More complicated questions about maxima and minima, and some closures of NP
• NP is as easy as detecting unique solutions
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On Isomorphisms and Density of NP and Other Complete Sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• On random reductions from sparse sets to tally sets
• On reductions of NP sets to sparse sets
• On self-reducibility and weak P-selectivity
• On Sets Truth-Table Reducible to Sparse Sets
• On sparse hard sets for counting classes
• On the Computational Complexity of Small Descriptions
• On unique satisfiability and the threshold behavior of randomized reductions
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Reducibilities on tally and sparse sets
• Reductions on NP and p-selective sets
• Relating Equivalence and Reducibility to Sparse Sets
• Relativizing relativized computations
• Self-reducibility
• Some consequences of non-uniform conditions on uniform classes
• Some observations on the probabilistic algorithms and NP-hard problems
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• SPARSE Reduces Conjunctively to TALLY
• The complexity of promise problems with applications to public-key cryptography
• Turing machines with few accepting computations and low sets for PP
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• Upper bounds for the complexity of sparse and tally descriptions

Cited in

(1)

• Sparse selfreducible sets and nonuniform lower bounds

This page was built for publication: Monotonous and randomized reductions to sparse sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4717050)