Polynomial-Time Membership Comparable Sets

DOI10.1137/S0097539793258131zbMath0835.68047OpenAlexW2062856555MaRDI QIDQ4857595

Ogihara, Mitsunori

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

zbMATH Keywords

P-selective setpolynomial-time computable functionpolynomial-time membership comparable sets

Mathematics Subject Classification ID

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

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