@inproceedings{Meer, author = {Meer, Klaus}, title = {Query languages for real number databases based on descriptive complexity over R}, series = {Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings}, booktitle = {Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings}, editor = {Kutylowski, Miroslaw and Leszek, Pacholski and Wierzbicki, Tomasz}, publisher = {Springer}, address = {Berlin [u.a.]}, isbn = {978-3-540-66408-6}, doi = {10.1007/3-540-48340-3_2}, pages = {12 -- 22}, abstract = {We propose the study of query languages for databases involving real numbers as data (called real number databases in the sequel). As main new aspect our approach is based on real number complexity theory as introduced in [8] and descriptive complexity for the latter developed in [17]. Using this formal framework a uniform treatment of query languages for such databases is obtained. Precise results about both the data- and the expression-complexity of several such query languages are proved. More explicitly, relying on descriptive complexity theory over ℝ gives the possibility to derive a hierarchy of complete languages for most of the important real number complexity classes. A clear correspondence between different logics and such complexity classes is established. In particular, it is possible to formalize queries involving in a uniform manner real spaces of different dimensions. This can be done in such a way that the logical description exactly reflects the computational complexity of a query. The latter might circumvent a problem appearing in some of the former approaches dealing with semi-algebraic databases (see [20] , [18]), where the use of first-order logic over real-closed fields can imply inefficiency as soon as the dimension of the underlying real space is not fixed - no matter whether the query under consideration is easy to compute or not.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {Computations over Z and R : a comparison}, series = {Journal of Complexity}, volume = {6}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1016/0885-064X(90)90022-6}, pages = {256 -- 263}, abstract = {Regarding real number models of computation may be a helpful way to get deeper insight into the classical theory over Z. Therefore it seems useful to study the complexity of classical problems in the real model. In this connection, the problem of deciding the existence of a nonnegative zero for certain polynomials plays an important part because a lot of NP-problems over Z can be polynomial reduced to it.}, language = {en} } @misc{Meer, author = {Meer, Klaus}, title = {A note on a \$ P \neq NP-\$ result in a restricted class of real machines}, series = {Journal of Complexity}, volume = {8}, journal = {Journal of Complexity}, number = {4}, issn = {0885-064X}, doi = {10.1016/0885-064X(92)90007-X}, pages = {451 -- 453}, abstract = {For a class of real machines using only linear functionals as computations and equality-tests, we show that the classes P and NP differ.}, language = {en} } @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} } @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} } @misc{GoriMeer, author = {Gori, Marco and Meer, Klaus}, title = {A step towards a complexity theory for analog systems.}, series = {Mathematical Logic Quarterly}, volume = {48}, journal = {Mathematical Logic Quarterly}, number = {Suppl. 1}, issn = {0942-5616}, pages = {45 -- 58}, language = {en} } @incollection{MakowskyMeer, author = {Makowsky, Janos A. and Meer, Klaus}, title = {Polynomials of bounded treewidth}, series = {Foundations of Computational Mathematics, Proceedings of the Smalefest 2000}, booktitle = {Foundations of Computational Mathematics, Proceedings of the Smalefest 2000}, editor = {Cucker, Felipe and Rojas, Maurice}, publisher = {World Scientific}, address = {Singapore}, isbn = {978-981-02-4845-1}, pages = {211 -- 250}, language = {en} } @misc{MatamalaMeer, author = {Matamala, Martin and Meer, Klaus}, title = {On the computational structure of the connected components of difficult sets}, series = {Information Processing Letters}, volume = {72}, journal = {Information Processing Letters}, number = {3-4}, issn = {0020-0190}, pages = {83 -- 90}, language = {en} } @misc{CuckerMeer, author = {Cucker, Felipe and Meer, Klaus}, title = {Logics which capture complexity classes over the reals}, series = {Journal of Symbolic Logic}, volume = {64}, journal = {Journal of Symbolic Logic}, number = {1}, issn = {0022-4812}, pages = {363 -- 390}, language = {en} } @misc{BenningElkoushyMeer, author = {Benning, Wilhelm and Elkoushy, Ashraf and Meer, Klaus}, title = {Innere-Punkt Methoden f{\"u}r die automatisierte Fehlersuche in geod{\"a}tischen Anwendungen (Interior point methods for automatic blunders detection in surveying)}, series = {Allgemeine Vermessungsnachrichten}, volume = {104}, journal = {Allgemeine Vermessungsnachrichten}, number = {8-9}, issn = {0002-5968}, pages = {319 -- 324}, language = {de} } @misc{MeerMichaux, author = {Meer, Klaus and Michaux, Christian}, title = {A Survey on Real Structural Complexity Theory}, series = {Bulletin of the Belgian Mathematical Society Simon Stevin}, volume = {4}, journal = {Bulletin of the Belgian Mathematical Society Simon Stevin}, number = {1}, issn = {1370-1444}, pages = {113 -- 148}, language = {en} } @misc{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {An algebraic proof of the real number PCP theorem}, series = {Journal of Complexity}, volume = {40}, journal = {Journal of Complexity}, issn = {0885-064X}, doi = {10.1016/j.jco.2016.11.006}, pages = {34 -- 77}, abstract = {The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora et al. (Arora et al., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition. We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models.}, language = {en} } @misc{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {Interactive proofs and a Shamir-like result for real number computations}, series = {Computational Complexity}, journal = {Computational Complexity}, issn = {1016-3328}, doi = {10.1007/s00037-018-0174-6}, pages = {33}, language = {en} } @inproceedings{BaartseMeer, author = {Baartse, Martijn and Meer, Klaus}, title = {Real Interactive Proofs for VPSPACE}, series = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH}, address = {Wadern}, isbn = {978-3-95977-016-3}, doi = {10.4230/LIPIcs.MFCS.2016.14}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-64300}, pages = {14.1 -- 14.13}, language = {en} } @inproceedings{MeerBaartse, author = {Meer, Klaus and Baartse, Martijn}, title = {Some results on interactive proofs for real computations}, series = {Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings}, booktitle = {Evolving Computability 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015, Proceedings}, editor = {Beckmann, Arnold and Mitrana, Victor and Soskova, Mariya}, publisher = {Springer International Publishing}, address = {Berlin [u.a.]}, isbn = {978-3-319-20027-9}, doi = {10.1007/978-3-319-20028-6}, pages = {107 -- 116}, language = {en} }