test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
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 http://www.cs.uwyo.edu/~jhitchco/bib/dim.shtml
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