681 research outputs found
On the computing power of +, -, and Ã
No full textModify the Blum-Shub-Smale model of computation replacing the permitted computational primitives (the real field operations) with any finite set B of real functions semialgebraic over the rationals. Consider the class of Boolean decision problems that can be solved in polynomial time in the new model by machines with no machine constants. How does this class depend on B? We prove that it is always contained in the class obtained for B = +,-, Ã. Moreover, if B is a set of continuous semialgebraic functions containing + and -, and such that arbitrarily small numbers can be computed using B, then we have the following dichotomy: either our class is P or it coincides with the class obtained for B = +,-, Ã. Copyright © 2014 ACM
Strategy recovery for stochastic mean payoff games
No full textWe prove that to find optimal positional strategies for stochastic mean payoff games when the value of every state of the game is known, in general, is as hard as solving such games tout court. This answers a question posed by Daniel Andersson and Peter Bro Miltersen
On the homotopy type of definable groups in an o-minimal structure
No full textWe consider definably compact groups in an o-minimal expansion of a real closed field. It is known that to each such group G is associated in a functorial way an intrinsic "infinitesimal subgroup" G(00) and a real Lie group G/G(00). We prove that that the isomorphism type of G/G(00) in the Lie category determines the definable homotopy type of G. In the semisimple case a stronger result holds, namely the definable isomorphism type of G is determined by the associated Lie group. The proof depends on the study of the homotopy properties of the projection of G onto the associated Lie group. It is shown in particular that the preimage of a simply connected open set is simply connected in the definable category. This will also allow us to show that there is a correspondence between finite group extensions in the Lie category and in the definable category
On the computational complexity of a game of cops and robbers
No full textWe study the computational complexity of a perfect-information two-player game proposed by Aigner and Fromme (1984) [1]. The game takes place on an undirected graph where n simultaneously moving cops attempt to capture a single robber, all moving at the same speed. The players are allowed to pick their starting positions at the first move. The question of the computational complexity of deciding this game was raised by Goldstein and Reingold (1995) [9]. We prove that the game is hard for PSPACE.©2012 Elsevier B.V. All rights reserved
Splitting definably compact groups in o-minimal structures
No full textAbstract. An argument of A. Borel [Bor–61, Proposition 3.1] shows that every compact connected Lie group is homeomorphic to the Cartesian product of its derived subgroup and a torus. We prove a parallel result for definably compact definably connected groups definable in an o-minimal expansion of a real closed field. As opposed to the Lie case, however, we provide an example showing that the derived subgroup may not have a definable semidirect complement. 1
Arithmetic of Dedekind cuts of ordered Abelian groups
No full textAbstractWe study Dedekind cuts on ordered Abelian groups. We introduce a monoid structure on them, and we characterise, via a suitable representation theorem, the universal part of the theory of such structures
Max-closed semilinear constraint satisfaction
No full textA semilinear relation S â ân is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in Mean Payoff Games, a notorious problem of open computational complexity. Mean Payoff Games are known to be in NPâ©co-NP, which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called tropically convex in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinear constraints in general into NP â© co-NP. This extends the corresponding complexity result for scheduling under and-or precedence constraints, or equivalently the max-atoms problem. To this end, we present a characterization of maxclosed semilinear relations in terms of syntactically restricted first-order logic, and another characterization in terms of a finite set of relations L that allow primitive positive definitions of all other relations in the class. We also present a subclass of max-closed constraints where the CSP is in P; this class generalizes the class of max-closed constraints over finite domains, and the feasibility problem for max-closed linear inequalities. Finally, we show that the class of max-closed semilinear constraints is maximal in the sense that as soon as a single relation that is not maxclosed is added to L, the CSP becomes NP-hard
Tropically Convex Constraint Satisfaction
No full textA semilinear relation (Formula presented.) is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in Mean Payoff Games, a notorious problem of open computational complexity. Mean Payoff Games are known to be in NP â© coâ NP, which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called tropically convex in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinear constraints in general into NP â© coâ NP. This extends the corresponding complexity result for scheduling under and-or precedence constraints, or equivalently the max-atoms problem. To this end, we present a characterization of max-closed semilinear relations in terms of syntactically restricted first-order logic, and another characterization in terms of a finite set of relations L that allow primitive positive definitions of all other relations in the class. We also present a subclass of max-closed constraints where the CSP is in P; this class generalizes the class of max-closed constraints over finite domains, and the feasibility problem for max-closed linear inequalities. Finally, we show that the class of max-closed semilinear constraints is maximal in the sense that as soon as a single relation that is not max-closed is added to L, the CSP becomes NP-hard
Asymptotic analysis of Skolem's exponential functions
No full textSkolem (1956) studied the germs at infinity of the smallest class of real valued functions on the positive real line containing the constant , the identity function , and such that whenever and are in the set, and are in the set. This set of germs is well ordered and Skolem conjectured that its order type is epsilon-zero. Van den Dries and Levitz (1984) computed the order type of the fragment below . Here we prove that the set of asymptotic classes within any archimedean class of Skolem functions has order type . As a consequence we obtain, for each positive integer , an upper bound for the fragment below . We deduce an epsilon-zero upper bound for the fragment below , improving the previous epsilon-omega bound by Levitz (1978). A novel feature of our approach is the use of Conway's surreal number for asymptotic calculations
- …
