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.

Export metadata

Additional Services

Search Google Scholar
Metadaten
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
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.