On the reducibility of sets inside NP to sets with low information content
type: Item
instance of: scholarly article
title: On the reducibility of sets inside NP to sets with low information content
zbMATH Open document ID: 1076.68032
author: Till Tantau
author: Ogihara, Mitsunori
published in: Journal of Computer and System Sciences
publication date: 2005-02-23T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2137319
zbMATH Keywords: Computational complexity
zbMATH Keywords: Selectivity
zbMATH Keywords: Membership comparability
zbMATH Keywords: Self-reduction
zbMATH Keywords: Sets with low information content
zbMATH Keywords: Prover-verifier protocols
MaRDI profile type: Publication
full work available at URL: j.jcss.2004.03.003
OpenAlex ID: W4240832909
cites work: A note on decision versus search for graph automorphism
cites work: Quasi-linear truth-table reductions to \(p\)-selective sets
cites work: A very hard log-space counting class
cites work: Q4281491
cites work: A structural property of regular frequency computations.
cites work: Regular frequency computations
cites work: Q4259996
cites work: Approximable sets
cites work: The (Non)enumerability of the determinant and the rank
cites work: \(p\)-selective self-reducible sets: a new characterization of P
cites work: Structure and importance of logspace-MOD class
cites work: Enumerative counting is hard
cites work: Division in logspace-uniform NC
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Cryptocomplexity and NP-completeness
cites work: On sparse sets in NP-P
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: NONDETERMINISTICALLY SELECTIVE SETS
cites work: Computing Solutions Uniquely Collapses the Polynomial Hierarchy
cites work: Optimal advice
cites work: Descriptive complexity: a logician's approach to computation.
cites work: On self-reducibility and weak P-selectivity
cites work: Q4273947
cites work: Relativization of questions about log space computability
cites work: A comparison of polynomial time reducibilities
cites work: Symmetric space-bounded computation
cites work: Q4281499
cites work: A note on the graph isomorphism counting problem
cites work: Q5585195
cites work: Q4808678
cites work: Q4234059
cites work: Polynomial-Time Membership Comparable Sets
cites work: Q4298260
cites work: Approximate formulas for some functions of prime numbers
cites work: On the density of families of sets
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: On membership comparable sets
cites work: On polynomial-time truth-table reducibility of intractable sets to P-selective sets
cites work: Q4036702
cites work: NP is as easy as detecting unique solutions
cites work: Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
DOI: 10.1016/J.JCSS.2004.03.003
Recommended article: Reductions to sets of low information content
Recommended article: On reductions of NP sets to sparse sets
Recommended article: Q4281491
Recommended article: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Recommended article: Comparing reductions to NP-complete sets
Recommended article: Comparing Reductions to NP-Complete Sets
Recommended article: Q4601894
Recommended article: Autoreducibility of NP-complete sets under strong hypotheses
Recommended article: Polynomial-time reducibilities and ``almost all'' oracle sets
Recommended article: Circuit-size lower bounds and non-reducibility to sparse sets
description: scientific article; zbMATH DE number 2137319