On membership comparable sets

MaRDI QIDQ1961377zbMATH OpenFDO

Authors Yanyan Li

Publication date 17 January 2000

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

UniqueSAT

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1335874
• Polynomial-Time Membership Comparable Sets
• Near-Testable Sets
• Query complexity of membership comparable sets.
• NP is as easy as detecting unique solutions

Cites work

• p-selective self-reducible sets: a new characterization of P
• p-Selective sets and reducing search to decision vs. self-reducibility
• A combinatorial problem; stability and order for models and theories in infinitary languages
• Approximable sets
• Enumerative counting is hard
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 3763833 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3494440 (Why is no real title available?)
• scientific article; zbMATH DE number 1256688 (Why is no real title available?)
• scientific article; zbMATH DE number 1304328 (Why is no real title available?)
• scientific article; zbMATH DE number 1306868 (Why is no real title available?)
• scientific article; zbMATH DE number 1306869 (Why is no real title available?)
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• scientific article; zbMATH DE number 1088261 (Why is no real title available?)
• scientific article; zbMATH DE number 1559564 (Why is no real title available?)
• scientific article; zbMATH DE number 1414313 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• On self-reducibility and weak P-selectivity
• On the density of families of sets
• On the existence of hard sparse sets under weak reductions
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Quantifying the amount of verboseness
• Reductions on NP and p-selective sets
• Short propositional formulas represent nondeterministic computations
• The complexity of promise problems with applications to public-key cryptography

Cited in

(9)

• Query complexity of membership comparable sets.
• Some connections between bounded query classes and non-uniform complexity.
• On the reducibility of sets inside NP to sets with low information content
• The enumerability of P collapses P to NC
• scientific article; zbMATH DE number 1335874 (Why is no real title available?)
• Polynomial-Time Membership Comparable Sets
• The communication complexity of enumeration, elimination, and selection
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Choosing, agreeing, and eliminating in communication complexity

This page was built for publication: On membership comparable sets

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