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.
Vasco Brattka, Guido Gherardi, Rupert Hölzl (2015). Las Vegas computability and algorithmic randomness. Dagstuhl : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik [10.4230/LIPIcs.STACS.2015.130].
Las Vegas computability and algorithmic randomness
GHERARDI, GUIDO;
2015
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
LasVegas-STACS15.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
659.99 kB
Formato
Adobe PDF
|
659.99 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.