|
NeuroCOLT
Technical Report NC-TR-98-011
How
many connected components must a difficult set have?
Martin Matamala
Universidad de Chile
Klaus Meer
RWTH
Aachen
Keywords:
Connected components; sparseness; real number complexity
Received:
MAY, 1998
Abstract
In this tutorial we seek to outline some of the features which
arise when analyzing the same computational problems in different
complexity theoretic frameworks. We focus on two problems:
- the first relates to mathematical optimization, and
- the second deals with the intrinsic structure of complexity classes.
Both examples serve well for examining how far different approaches
to the same problem may shed light upon each other, but also allow
the application of intrinsically different methods focussing on other
aspects, sometimes leading to diverse results.
Download Compressed Postscript
|