Logical Approaches to Computational Barriers

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 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 | 2006-07-05 |