๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the complexity of finite random functions

โœ Scribed by Uriel Feige

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
158 KB
Volume
44
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
โœ K. Sutner ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N

Bounding the Complexity of Advice Functi
Bounding the Complexity of Advice Functions
โœ R. Gavalda ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 624 KB

It was known that every set \(\boldsymbol{A}\) in \(P\) poly has an advice function in \(\operatorname{PF}\left(\Sigma_{2}^{p}(A)\right)\). This paper shows that \(A\) also has an advice function in \(\operatorname{PF}\left(\operatorname{NP}(A) \oplus \Sigma_{3}^{p}\right)\). From this new bound, it

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
โœ Luc Devroye; Carlos Zamora-Cura ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 256 KB ๐Ÿ‘ 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co