P^f is not equal to NP^f for almost all f

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines P^f = NP^f can be true for any function f from the reals into omega_1. We show that ``almost everywhere'' the answer is negative.
11 pages

Keywords

Logic, 03D30; 03D60; 03D15; 68Q15

Citation

URI

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

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0212046
 http://arxiv.org/abs/math/0212046

Collections

arXiv