𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Quantum Query Complexity of Local Search in

✍ Scribed by Xiaoming Sun; Andrew Chi-Chih Yao

Publisher
Springer
Year
2008
Tongue
English
Weight
539 KB
Volume
55
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the query complexity of finding a loc
On the query complexity of finding a local maximum point
✍ A.L. Rastsvetaev; L.D. Beklemishev πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 94 KB

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M 1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.

The Complexity of Local Proof Search in
The Complexity of Local Proof Search in Linear Logic: (Extended Abstract)
✍ Patrick D. Lincoln; John C. Mitchell; Andre Scedrov πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 473 KB

Proof search in linear logic is known to be di cult: the provability of propositional linear logic formulas is undecidable. Even without the modalities, multiplicativeadditive fragment of propositional linear logic, mall, i s k n o wn to be pspace-complete, and the pure multiplicative fragment, mll,