On the relations between discrete and continuous complexity theory
- 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.
Author: | Klaus MeerGND |
---|---|
URL: | http://onlinelibrary.wiley.com/doi/10.1002/malq.19950410214/abstract |
DOI: | https://doi.org/10.1002/malq.19950410214 |
ISSN: | 0885-064X |
Title of the source (English): | Mathematical Logic Quarterly |
Document Type: | Scientific journal article peer-reviewed |
Language: | English |
Year of publication: | 1995 |
Tag: | 3-Satisfiability; Exponential-time computations; Real model of computation; Sparseness |
Volume/Year: | 41 |
Issue number: | 2 |
First Page: | 281 |
Last Page: | 286 |
Faculty/Chair: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik |