Approximate Query Complexity
ACM Transactions on Computation Theory · 2011
DOI: 10.1145/2003685.2003688 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von Clifford Smyth. Die Arbeit nennt 12 Literaturangaben.
Abstract (Originalsprache)
Let f : {0, 1} n → {0, 1}. Let μ be a product probability measure on {0, 1} n . For ϵ ≥ 0, we define Dϵ ( f ), the ϵ-approximate decision tree complexity of f , to be the minimum depth of a decision tree T with μ ( T ( x ) ≠ f ( x )) ≤ ϵ . For j = 0 or 1 and for δ ≥ 0, we define Cj,δ ( f ), the δ-approximate j -certificate complexity of f , to be the minimum certificate complexity of a set A ⊆ Ω with μ ( AΔf −1 ( j )) ≤ ϵ . Note that if μ ( x ) > 0 for all x then D 0 ( f ) = D ( f ) and Cj ,0 ( f ) = Cj ( f ) are the ordinary decision tree and j -certificate complexities of f , respectively. We extend the well-known result, D ( f ) ≤ C 1 ( f ) C 0 ( f ) [Blum and Impagliazzo 1987; Hartmanis and Hemachandra 1991; Tardos 1989], proving that for all ϵ > 0 there exists a δ > 0 and a constant K = K ( ϵ , δ ) > 0 such that for all n , μ , f , Dϵ ( f ) ≤ K C 1, δ ( f ) C 0, δ ( f ). We also give a partial answer to a related question on query complexity raised by Tardos [1989]. We prove generalizations of these results to general product probability spaces.
Zitieren
APA
Smyth, C. (2011). Approximate Query Complexity. ACM Transactions on Computation Theory. https://doi.org/10.1145/2003685.2003688
Vancouver
Smyth C. Approximate Query Complexity. ACM Transactions on Computation Theory. 2011. doi:10.1145/2003685.2003688
BibTeX
@article{Smyth2011,
author = {Smyth, Clifford},
title = {Approximate Query Complexity},
journal = {ACM Transactions on Computation Theory},
year = {2011},
doi = {10.1145/2003685.2003688}
}
EUVIMED