Query complexity of membership comparable sets.

DOI10.1016/S0304-3975(03)00082-3MaRDI QIDQ1401341zbMATH OpenFDO

Authors Till Tantau

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(03)00082-3

zbMATH Keywords

Membership comparableP-selectiveQuery complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polynomial-Time Membership Comparable Sets
• The complexity of ODD_n^A
• scientific article; zbMATH DE number 1114037
• scientific article; zbMATH DE number 1263194
• scientific article; zbMATH DE number 512828

Cites work

• A comparison of polynomial time reducibilities
• Approximable sets
• scientific article; zbMATH DE number 3494440 (Why is no real title available?)
• On membership comparable sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• On self-reducibility and weak P-selectivity
• On sets Turing reducible to p-selective sets
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Polynomial-Time Membership Comparable Sets
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Reconstructing Algebraic Functions from Mixed Data
• Reducibility classes of P-selective sets
• Reductions on NP and p-selective sets
• The complexity of ODD_n^A

Cited in

(5)

• On membership comparable sets
• scientific article; zbMATH DE number 1335874 (Why is no real title available?)
• scientific article; zbMATH DE number 512828 (Why is no real title available?)
• scientific article; zbMATH DE number 1114037 (Why is no real title available?)
• Polynomial-Time Membership Comparable Sets

This page was built for publication: Query complexity of membership comparable sets.

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