Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. We also study some features of probability weight of correctness with respect to generalizations of Procaccia and Rosenschein's junta distributions [PR07b].

Keywords

Computational Complexity, Computer Science and Game Theory, Multiagent Systems, F.1.3; F.2.2; I.2.11

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/163007

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0806.2555
 http://arxiv.org/abs/0806.2555

Collections

arXiv