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 (21)

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

This page was built for publication: Polynomial-Time Membership Comparable Sets