On the reducibility of sets inside NP to sets with low information content

DOI10.1016/j.jcss.2004.03.003zbMath1076.68032OpenAlexW4240832909MaRDI QIDQ1765294

Till Tantau, Ogihara, Mitsunori

Publication date: 23 February 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.03.003

zbMATH Keywords

Computational complexitySelectivityMembership comparabilityProver-verifier protocolsSelf-reductionSets with low information content

Mathematics Subject Classification ID

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

Related Items (3)

Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ The value of help bits in randomized and average-case complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal advice
• A note on decision versus search for graph automorphism
• On self-reducibility and weak P-selectivity
• NP is as easy as detecting unique solutions
• Symmetric space-bounded computation
• On sparse sets in NP-P
• A very hard log-space counting class
• A comparison of polynomial time reducibilities
• A note on the graph isomorphism counting problem
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• Quasi-linear truth-table reductions to \(p\)-selective sets
• The (Non)enumerability of the determinant and the rank
• \(p\)-selective self-reducible sets: a new characterization of P
• Enumerative counting is hard
• A structural property of regular frequency computations.
• Approximable sets
• On membership comparable sets
• On the density of families of sets
• Approximate formulas for some functions of prime numbers
• Division in logspace-uniformNC¹
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• The complexity of promise problems with applications to public-key cryptography
• Cryptocomplexity and NP-completeness
• Structure and importance of logspace-MOD class
• Relativization of questions about log space computability
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Polynomial-Time Membership Comparable Sets
• NONDETERMINISTICALLY SELECTIVE SETS
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: On the reducibility of sets inside NP to sets with low information content