@misc{Meer, author = {Meer, Klaus}, title = {Real number models under various sets of operations}, series = {Journal of Complexity}, volume = {9}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1006/jcom.1993.1023}, pages = {366 -- 372}, abstract = {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.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Real number models : on the use of information}, series = {Journal of Symbolic Computation}, volume = {18}, journal = {Journal of Symbolic Computation}, number = {3}, issn = {0747-7171}, doi = {10.1006/jsco.1994.1044}, pages = {199 -- 206}, abstract = {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.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On the complexity of Quadratic Programming in real number models of computation}, series = {Theoretical Computer Science}, volume = {133}, journal = {Theoretical Computer Science}, number = {1}, issn = {0304-3975}, doi = {10.1016/0304-3975(94)00070-0}, pages = {85 -- 94}, abstract = {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.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {On the relations between discrete and continuous complexity theory}, series = {Mathematical Logic Quarterly}, volume = {41}, journal = {Mathematical Logic Quarterly}, number = {2}, issn = {0885-064X}, doi = {10.1002/malq.19950410214}, pages = {281 -- 286}, 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.}, language = {en} } @misc{MeerLickteig, author = {Meer, Klaus and Lickteig, Thomas}, title = {A note on testing the resultant}, series = {Journal of Complexity}, volume = {11}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1006/jcom.1995.1016}, pages = {344 -- 351}, abstract = {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.}, language = {en} } @inproceedings{MeerSchreiber, author = {Meer, Klaus and Schreiber, Harold}, title = {Maßsynthese vier- sechs- und achtgliedriger ebener Kurbelgetriebe und ihre Anwendung im Kfz-Karosseriebau}, series = {Kurvengetriebe, Koppelgetriebe, gesteuerte Antriebe, Probleml{\"o}sungen in der Bewegungstechnik, Conference Veitsh{\"o}chheim 26. and 27. September 2000, VDI-Getriebetagung 2000}, booktitle = {Kurvengetriebe, Koppelgetriebe, gesteuerte Antriebe, Probleml{\"o}sungen in der Bewegungstechnik, Conference Veitsh{\"o}chheim 26. and 27. September 2000, VDI-Getriebetagung 2000}, publisher = {VDI Verlag}, address = {D{\"u}sseldorf}, isbn = {3-18-091567-6}, pages = {277 -- 297}, language = {de} } @inproceedings{MakowskyMeer, author = {Makowsky, Janos A. and Meer, Klaus}, title = {On the complexity of combinatorial and metafinite generating functions}, series = {Computer science logic, 14th international workshop, proceedings, CSL 2000, Fischbachau, Germany, August 21 - 26, 2000}, booktitle = {Computer science logic, 14th international workshop, proceedings, CSL 2000, Fischbachau, Germany, August 21 - 26, 2000}, editor = {Clote, Peter and Schwichtenberg, Helmut}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-67895-6}, pages = {399 -- 410}, language = {en} } @inproceedings{MakowskyMeer, author = {Makowsky, Janos A. and Meer, Klaus}, title = {Polynomials of bounded tree-width}, series = {Formal Power Series and Algebraic Combinatorics, Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, June 2000}, booktitle = {Formal Power Series and Algebraic Combinatorics, Proceedings of the 12th International Conference, FPSAC'00, Moscow, Russia, June 2000}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {3-540-67247-8}, pages = {692 -- 703}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Counting problems over the reals.}, series = {Theoretical Computer Science}, volume = {242}, journal = {Theoretical Computer Science}, number = {1-2}, issn = {0304-397}, pages = {41 -- 58}, language = {en} } @misc{BenDavidMeerMichaux, author = {Ben-David, Shai and Meer, Klaus and Michaux, Christian}, title = {A note on non-complete problems in NP_R.}, series = {Journal of Complexity}, volume = {16}, journal = {Journal of Complexity}, number = {1}, issn = {0885-064X}, pages = {324 -- 332}, language = {en} }