Premium
On the Relations Between Discrete and Continuous Complexity Theory
Author(s) -
Meer Klaus
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410214
Subject(s) - satisfiability , mathematics , exponential function , computation , computational complexity theory , discrete mathematics , boolean satisfiability problem , theoretical computer science , algebra over a field , algorithm , computer science , pure mathematics , mathematical analysis
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.