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.
Las Vegas computability and algorithmic randomness / Vasco Brattka; Guido Gherardi; Rupert Hölzl. - ELETTRONICO. - (2015), pp. 130-142. (Intervento presentato al convegno STACS 2015 tenutosi a München nel 04/07/2015-07/03/2015) [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.