TY - GEN A1 - Meer, Klaus A1 - Michaux, Christian T1 - A Survey on Real Structural Complexity Theory T2 - Bulletin of the Belgian Mathematical Society Simon Stevin Y1 - 1997 SN - 1370-1444 VL - 4 IS - 1 SP - 113 EP - 148 ER - TY - CHAP A1 - Cucker, Felipe A1 - Meer, Klaus T1 - Logics which capture complexity classes over the reals T2 - Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS '97 Bratislava, Slovakia, August 25-29, 1997 Proceedings Y1 - 1997 SP - 398 EP - 407 PB - Springer CY - Heidelberg ER - TY - CHAP A1 - Meer, Klaus ED - Prívara, Igor ED - Ružička, Peter T1 - Counting problems over the reals T2 - Mathematical foundations of computer science 1997, 22nd international symposium, proceedings, MFCS '97, Bratislava, Slovakia, August 25 - 29, 1997 N2 - In this paper we introduce a complexity theoretic notion of counting problems over the real numbers. We follow the approaches of Blum, Shub, and Smale. Y1 - 1997 UR - http://www.springer.com/us/book/9783540634379?wt_mc=ThirdParty.SpringerLink.3.EPR653.About_eBook SN - 978-3-540-63437-9 U6 - https://doi.org/10.1007/BFb0029983 SP - 398 EP - 407 PB - Springer CY - Berlin [u.a.] ER - TY - GEN A1 - Meer, Klaus T1 - On the relations between discrete and continuous complexity theory T2 - Mathematical Logic Quarterly N2 - 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. KW - Real model of computation KW - 3-Satisfiability KW - Sparseness KW - Exponential-time computations Y1 - 1995 UR - http://onlinelibrary.wiley.com/doi/10.1002/malq.19950410214/abstract U6 - https://doi.org/10.1002/malq.19950410214 SN - 0885-064X VL - 41 IS - 2 SP - 281 EP - 286 ER - TY - GEN A1 - Meer, Klaus A1 - Lickteig, Thomas T1 - A note on testing the resultant T2 - Journal of Complexity N2 - Shub (in "From Topology to Computation: Proceedings of the Smalefest." (M. Hirsch, J. Marsden, and M. Shub, Eds.), pp. 281-301, Springer-Verlag, New York/Berlin, 1993) proposes to attack the complex PFull-size image (<1 K) versus the NPFull-size image (<1 K) problem by focussing on lower bounds on testing the resultant of quadratic forms for zero. Taking up this question we show in the present paper a lower bound of order n3 for the resultant. Y1 - 1995 UR - http://www.sciencedirect.com/science/article/pii/S0885064X85710163?np=y U6 - https://doi.org/10.1006/jcom.1995.1016 SN - 0885-064X VL - 11 IS - 3 SP - 344 EP - 351 ER - TY - CHAP A1 - Grädel, Erich A1 - Meer, Klaus T1 - Descriptive Complexity Theory over the real numbers T2 - Proceedings of the 27th Annual ACM Symposium on Theory of Computing STOC, Las Vegas, 1995 Y1 - 1995 U6 - https://doi.org/10.1145/225058.225151 SP - 315 EP - 324 PB - ACM CY - New York, NY ER - TY - GEN A1 - Meer, Klaus T1 - Real number models : on the use of information T2 - Journal of Symbolic Computation N2 - When comparing complexity theory over the ring Z (Turing machine) on one hand and over the ring R (Blum-Shub-Smale machine) on the other hand, it will be important to study how methods and ideas of the first can be transformed to the second one. In this sense the present paper is concerned with the relation between a characterization of the P = NP?-question for the Z-case (given by Krentel) and a special class of quadratic-programming problems which are important in the real model. Y1 - 1994 UR - http://www.sciencedirect.com/science/article/pii/S0747717184710443 U6 - https://doi.org/10.1006/jsco.1994.1044 SN - 0747-7171 VL - 18 IS - 3 SP - 199 EP - 206 ER - TY - GEN A1 - Meer, Klaus T1 - On the complexity of Quadratic Programming in real number models of computation T2 - Theoretical Computer Science N2 - The complexity of linearly constrained (nonconvex) quadratic programming is analyzed within the framework of real number models, namely the one of Blum, Shub, and Smale and its modification recently introduced by Koiran (“weak BSS-model”). In particular we show that this problem is not NP-complete in the Koiran setting. Applications to the (full) BSS-model are discussed. Y1 - 1994 UR - http://www.sciencedirect.com/science/article/pii/0304397594000700 U6 - https://doi.org/10.1016/0304-3975(94)00070-0 SN - 0304-3975 VL - 133 IS - 1 SP - 85 EP - 94 ER - TY - GEN A1 - Meer, Klaus T1 - Real number models under various sets of operations T2 - Journal of Complexity N2 - The computational model of Blum, Shub, and Smale (1989, Bull. Amer. Math. Soc.21, 1-46) yields a numerous number of different algorithm-classes if the allowed set of instructions is varied. For two such classes we consider the "P = NP?" problem as well as the question of whether the NP- problems are decidable. Y1 - 1993 UR - http://www.sciencedirect.com/science/article/pii/S0885064X8371023X U6 - https://doi.org/10.1006/jcom.1993.1023 SN - 0885-064X VL - 9 IS - 3 SP - 366 EP - 372 ER - TY - GEN A1 - Meer, Klaus T1 - A note on a $ P \neq NP-$ result in a restricted class of real machines T2 - Journal of Complexity N2 - For a class of real machines using only linear functionals as computations and equality-tests, we show that the classes P and NP differ. Y1 - 1992 UR - http://www.sciencedirect.com/science/article/pii/0885064X9290007X U6 - https://doi.org/10.1016/0885-064X(92)90007-X SN - 0885-064X VL - 8 IS - 4 SP - 451 EP - 453 ER -