Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Abstract by a firstorder quantifierfree formula in the language of the reals, the goal is to output a simplicial complex$S \subset \mathbb {R}^k$ , whose geometric realization,$\Delta $ , is semialgebraically homeomorphic to$\Delta $ S . In this paper, we consider a weaker version of this question. We prove that for any , there exists an algorithm which takes as input a description of a semialgebraic subset$\ell \geq 0$ given by a quantifierfree firstorder formula$S \subset \mathbb {R}^k$ in the language of the reals and produces as output a simplicial complex$\phi $ , whose geometric realization,$\Delta $ is$\Delta $ equivalent to$\ell $ S . The complexity of our algorithm is bounded by , where$(sd)^{k^{O(\ell )}}$ s is the number of polynomials appearing in the formula , and$\phi $ d a bound on their degrees. For fixed , this bound is$\ell $ singly exponential ink . In particular, since equivalence implies that the$\ell $ homotopy groups up to dimension of$\ell $ are isomorphic to those of$\Delta $ S , we obtain a reduction (having singly exponential complexity) of the problem of computing the first homotopy groups of$\ell $ S to the combinatorial problem of computing the first homotopy groups of a finite simplicial complex of size bounded by$\ell $ .$(sd)^{k^{O(\ell )}}$ 
Abstract Given a sequence $\{Z_d\}_{d\in \mathbb{N}}$ of smooth and compact hypersurfaces in ${\mathbb{R}}^{n1}$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$ such that each manifold $Z_d$ is diffeomorphic to a component of the zero set on $\Gamma$ of some polynomial of degree $d$. (This is in sharp contrast with the case when $\Gamma$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $p$ on $\Gamma$ is bounded by a polynomial in $\deg (p)$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$ containing a subset $D$ homeomorphic to a disk, and a family of polynomials $\{p_m\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that $(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n1}, Z_{d_m}),$ i.e. the zero set of $p_m$ in $D$ is isotopic to $Z_{d_m}$ in ${\mathbb{R}}^{n1}$. This says that, up to extracting subsequences, the intersection of $\Gamma$ with a hypersurface of degree $d$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $0 \leq k \leq n2$ and every sequence of natural numbers $a=\{a_d\}_{d\in \mathbb{N}}$ there is a regular, compact semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$, a subsequence $\{a_{d_m}\}_{m\in \mathbb{N}}$ and homogeneous polynomials $\{p_{m}\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $b_k$ denotes the $k$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $\Gamma$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $d$, of the set $\Sigma _{d_m,a, \Gamma }$ of polynomials verifying (0.1) is positive, but there exists a constant $c_\Gamma$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $a$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $\Gamma$, for most polynomials a Bézouttype bound holds for the intersection $\Gamma \cap Z(p)$: for every $0\leq k\leq n2$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n1}{2}}}.\end{equation*}$$

Free, publiclyaccessible full text available September 30, 2024

Free, publiclyaccessible full text available May 1, 2024

We introduce a notion of complexity of diagrams (and, in particular, of objects and morphisms) in an arbitrary category, as well as a notion of complexity of functors between categories equipped with complexity functions. We discuss several examples of this new definition in categories of wide common interest such as finite sets, Boolean functions, topological spaces, vector spaces, semilinear and semialgebraic sets, graded algebras, affine and projective varieties and schemes, and modules over polynomial rings. We show that on one hand categorical complexity recovers in several settings classical notions of nonuniform computational complexity (such as circuit complexity), while on the other hand it has features that make it mathematically more natural. We also postulate that studying functor complexity is the categorical analog of classical questions in complexity theory about separating different complexity classes.more » « less