2026-07-21T19:26:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4909 2024-03-06T10:35:31Z ddc:004 open_access

Las Vegas Computability and Algorithmic Randomness Brattka, Vasco Gherardi, Guido Hölzl, Rupert Weihrauch degrees weak weak König's lemma Las Vegas computability algorithmic randomness Nash equilibria In this article we try to formalize the question "What can be computed with access to randomness?" We propose the very fine-grained Weihrauch lattice as an approach to differentiate between different types of computation with access to randomness. In particular, we show that a natural concept of Las Vegas computability on infinite objects is more powerful than mere oracle access to a Martin-Löf random object. As a concrete problem that is Las Vegas computable but not computable with access to a Martin-Löf random oracle we study the problem of finding Nash equilibria. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vasco Brattka and Guido Gherardi and Rupert Hölzl 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.130 urn:nbn:de:0030-drops-49093 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.130 eng https://creativecommons.org/licenses/by/3.0/legalcode