Computability in Europe 2006
Logical Approaches to Computational Barriers

Invited Plenary Talk:
Two open problems on effective dimension

Speaker: Elvira Mayordomo


The talk main objective is to motivate the definition of effective dimension and
its applications in Computational Complexity, Information Theory and Fractal
Geometry. Please check the slides for more information and the bibliography page
maintained by John Hitchcock at

The proceedings content is the following.
In this note we propose two interesting open problems on
Computational Complexity, both related to  polynomial-time
reductions. Complete or partial solutions of these problems imply a
big advance in what we know on the classes NP and BPP.
 In both cases
quantitative methods such as resource-bounded measure have given
initial answers in the past, and the fact that dimension is defined
for every class can overcome non-measurability obstacles. 

websites: Arnold Beckmann 2006-07-05