|
NeuroCOLT
Technical Report NC-TR-95-012
On
the relations between discrete and continuous complexity theory
Klaus
Meer
RWTH Aachen
Abstract
Relations between discrete and continuous complexity models are considered.
The present paper is devoted to combine both models. In particular
we analyze the 3-Satisfiability problem. The existence of fast decision
procedures for this problem over the reals is examined based on certain
conditions on the discrete setting. Moreover we study the behaviour
of exponential time computations over the reals depending on the real
complexity of 3-Satisfiability. This will be done using tools from
complexity theory over the integers.
Download Compressed
Postscript
|