Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-138 | 17th September 2010 20:17

Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

RSS-Feed




TR10-138
Authors: Eric Allender, Luke Friedman, William Gasarch
Publication: 17th September 2010 20:17
Downloads: 2097
Keywords: 


Abstract:

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at most i such that U(d)=x}. This result is relevant for some recent complexity-theoretic investigations undertaken by the authors.



ISSN 1433-8092 | Imprint