On membership comparable sets
From MaRDI portal
Publication:1961377
zbMath0948.68086MaRDI QIDQ1961377
Publication date: 17 January 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (7)
Query complexity of membership comparable sets. ⋮ Singleton-type bounds for list-decoding and list-recovery, and related results ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ The enumerability of P collapses P to NC
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On self-reducibility and weak P-selectivity
- NP is as easy as detecting unique solutions
- Short propositional formulas represent nondeterministic computations
- Factoring polynomials with rational coefficients
- Reductions on NP and p-selective sets
- \(p\)-Selective sets and reducing search to decision vs. self-reducibility
- \(p\)-selective self-reducible sets: a new characterization of P
- Enumerative counting is hard
- Quantifying the amount of verboseness
- Approximable sets
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- The complexity of promise problems with applications to public-key cryptography
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- On the existence of hard sparse sets under weak reductions
This page was built for publication: On membership comparable sets
