Query complexity of membership comparable sets.

DOI10.1016/S0304-3975(03)00082-3zbMath1044.68063MaRDI QIDQ1401341

Till Tantau

Publication date: 17 August 2003

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

zbMATH Keywords

Membership comparableP-selectiveQuery complexity

Mathematics Subject Classification ID

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

Cites Work

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

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