Polynomial-Time Membership Comparable Sets
From MaRDI portal
Publication:4857595
DOI10.1137/S0097539793258131zbMath0835.68047OpenAlexW2062856555MaRDI QIDQ4857595
Publication date: 29 November 1995
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793258131
Related Items
NP-hard sets are superterse unless NP is small, Sparse sets, approximable sets, and parallel queries to NP, Geometric sets of low information content, Quasi-linear truth-table reductions to \(p\)-selective sets, Time bounded frequency computations, Query complexity of membership comparable sets., Some connections between bounded query classes and non-uniform complexity., Reducibility classes of P-selective sets, Some results on selectivity and self-reducibility, P-selectivity: Intersections and indices, Sparse selfreducible sets and nonuniform lower bounds, On the reducibility of sets inside NP to sets with low information content, The value of help bits in randomized and average-case complexity, The communication complexity of enumeration, elimination, and selection, On the size of classes with weak membership properties, Boolean operations, joins, and the extended low hierarchy, Some structural properties of SAT, One query reducibilities between partial information classes, The enumerability of P collapses P to NC, Commutative queries, Optimal series-parallel trade-offs for reducing a function to its own graph
