We discuss several complexity measures for boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest g...
详细信息
We discuss several complexity measures for boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of booleanfunctions on deterministic, randomized, and quantum computers. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论