6533b82cfe1ef96bd128f3e4
RESEARCH PRODUCT
Non-intersecting Complexity
Aleksandrs Belovssubject
PHCombinatoricsAverage-case complexityStructural complexity theoryAsymptotic computational complexityWorst-case complexityComplexity classDescriptive complexity theoryQuantum complexity theoryMathematicsdescription
A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2006-01-01 |