Polynomial-Time Membership Comparable Sets

DOI10.1137/S0097539793258131MaRDI QIDQ4857595zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Query complexity of membership comparable sets.
• On membership comparable sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• scientific article; zbMATH DE number 1335874
• Reducibility classes of P-selective sets

Cited in

(23)

• Commutative queries
• Optimal series-parallel trade-offs for reducing a function to its own graph
• scientific article; zbMATH DE number 1543037 (Why is no real title available?)
• On the reducibility of sets inside NP to sets with low information content
• Quasi-linear truth-table reductions to \(p\)-selective sets
• One query reducibilities between partial information classes
• The enumerability of P collapses P to NC
• Query complexity of membership comparable sets.
• Some connections between bounded query classes and non-uniform complexity.
• NP-hard sets are superterse unless NP is small
• Sparse sets, approximable sets, and parallel queries to NP
• Sparse selfreducible sets and nonuniform lower bounds
• Time bounded frequency computations
• P-selectivity: Intersections and indices
• The value of help bits in randomized and average-case complexity
• On the size of classes with weak membership properties
• The communication complexity of enumeration, elimination, and selection
• Boolean operations, joins, and the extended low hierarchy
• On membership comparable sets
• Geometric sets of low information content
• Some structural properties of SAT
• Reducibility classes of P-selective sets
• Some results on selectivity and self-reducibility

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4857595)