On the Relations Between Discrete and Continuous Complexity Theory

Mathematical Logic Quarterly 41 (2):281-286 (1995)
  Copy   BIBTEX

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

Categories

Keywords

Reprint years

DOI

10.1002/malq.19950410214

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,752

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
Satisfiability of formulae with one ∀ is decidable in exponential time.Erich Grädel - 1990 - Archive for Mathematical Logic 29 (4):265-276.
Grounding analog computers.Bruce J. MacLennan - unknown
Exponential state estimator design for discrete-time neural networks with discrete and distributed time-varying delays.Qihui Duan, Ju H. Park & Zheng-Guang Wu - 2014 - Complexity 20 (1):38-48.
Neural Computation and the Computational Theory of Cognition.Gualtiero Piccinini & Sonya Bahar - 2013 - Cognitive Science 37 (3):453-488.
The complexity of hybrid logics over equivalence relations.Martin Mundhenk & Thomas Schneider - 2009 - Journal of Logic, Language and Information 18 (4):493-514.
Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Grounding analog computers commentary on Harnad on symbolism- connectionism.Bruce J. MacLennan - unknown
Small substructures and decidability issues for first-order logic with two variables.Emanuel Kieroński & Martin Otto - 2012 - Journal of Symbolic Logic 77 (3):729-765.
On the nature of minds, or: Truth and consequences.Shimon Edelman - 2008 - Journal of Experimental and Theoretical Ai 20:181-196.
Continuous formal systems: A unifying model in language and cognition.Bruce J. MacLennan - unknown
Complexity Results for Modal Dependence Logic.Peter Lohmann & Heribert Vollmer - 2013 - Studia Logica 101 (2):343-366.
Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra.Martin Ziegler - 2012 - Annals of Pure and Applied Logic 163 (8):1108-1139.

Analytics

Added to PP
2013-12-01

Downloads
25 (#630,588)

6 months
4 (#778,909)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

No references found.

Add more references