Recent zbMATH articles in MSC 68Q15https://zbmath.org/atom/cc/68Q152023-09-22T14:21:46.120933ZWerkzeugImplicit computation complexity in higher-order programming languages. A survey in memory of Martin Hofmannhttps://zbmath.org/1517.680752023-09-22T14:21:46.120933Z"Dal Lago, U."https://zbmath.org/authors/?q=ai:dal-lago.ugoSummary: This paper is meant to be a survey about implicit characterizations of complexity classes by fragments of higher-order programming languages, with a special focus on type systems and subsystems of linear logic. Particular emphasis will be put on Martin Hofmann's contributions to the subject, which very much helped in shaping the field.Descriptive complexity of deterministic polylogarithmic time and spacehttps://zbmath.org/1517.681402023-09-22T14:21:46.120933Z"Ferrarotti, Flavio"https://zbmath.org/authors/?q=ai:ferrarotti.flavio-antonio"González, Senén"https://zbmath.org/authors/?q=ai:gonzalez.senen"Turull Torres, José María"https://zbmath.org/authors/?q=ai:turull-torres.jose-maria"Van den Bussche, Jan"https://zbmath.org/authors/?q=ai:van-den-bussche.jan"Virtema, Jonni"https://zbmath.org/authors/?q=ai:virtema.jonniThis paper presents model-theoretic representations of POLYLOGTIME and POLYLOGSPACE and, to this end, presents a variant of the Random Access Machine, called the ``Direct Access Machine'', and an associated logic, called ``Index Logic''. Given a finite ordered structure \(\mathbf A = (A, R_1^{\mathbf A}, \ldots, R_p^{\mathbf A}, c_1^{\mathbf A}, \ldots, c_q^{\mathbf A}, f_1^{\mathbf A}, \ldots, f_s^{\mathbf A})\) of binary encoding \(\operatorname{bin}(\mathbf A)\), where \(A\) has \(n\) elements and \(\operatorname{bin}(\mathbf A)\) has \(\hat{n}\), a direct access machine has \(r_i\) ``address'' work tapes for each \(r_i\)-ary relation \(R_i\), \(k_j\) ``address'' work tapes for each \(k_j\)-argument function \(f_j\) (along with a read-only ``value tape'' for each function), \(q + 1\) tapes for the \(q\) constants, plus several other work tapes, and the mechanism is designed to (passively) enforce logarithmic space bounds on the tapes.
If the binary code of an \(r_i\)-tuple \(\mathbf x\) is entered on the address work tape for \(R_i\), the machine produces the value \(0\) or \(1\), depending on whether or not \(\mathbf A, \mathbf x \models R_i\) and the state transition function for that tape uses that value in computing the next state and determining head movement on that tape. Similarly, if the binary code of a \(k_j\)-tuple \(\mathbf y\) is entered on the address work tape for \(f_j\), the binary code for \(f_j(\mathbf y)\) spontaneously appears on the \(j\)th value tape, which can then be used in the computation. The operation for constants is similar.
Index Logic has two sorts of variables, those that range over the domain of the input structure and those that range over \(\operatorname{Num}(\mathbf A) = \{ 0, 1, \ldots, \lceil \log n \rceil - 1 \}\) (where \(n\) is the cardinality of the domain of the input structure). The syntax is typical for a fixed-point logic, except for terms for accessing \(A\)-valued elements of given binary representations (and vice versa) and that fixed points are derived for \(\operatorname{Num}(\mathbf A)\)-valued variables.
Once these constructions are completed, the article presents proofs that Index Logic + Inflationary Fixed Point captures POLYLOGTIME (using direct access machines) and that Index Logic + Partial Fixed Point captures POLYLOGSPACE (random access machines may be used here).
Reviewer: Gregory Loren McColm (Tampa)\(\forall\exists\mathbb {R}\)-completeness and area-universalityhttps://zbmath.org/1517.682902023-09-22T14:21:46.120933Z"Dobbins, Michael Gene"https://zbmath.org/authors/?q=ai:dobbins.michael-gene"Kleist, Linda"https://zbmath.org/authors/?q=ai:kleist.linda"Miltzow, Tillmann"https://zbmath.org/authors/?q=ai:miltzow.tillmann"Rzążewski, Paweł"https://zbmath.org/authors/?q=ai:rzazewski.pawelSummary: In the study of geometric problems, the complexity class \(\exists\mathbb{R}\) plays a crucial role since it exhibits a deep connection between purely geometric problems and real algebra. Sometimes \(\exists\mathbb {R}\) is referred to as the ``real analogue'' to the class NP. While NP is a class of computational problems that deals with existentially quantified Boolean variables, \(\exists\mathbb{R}\) deals with existentially quantified real variables.
In analogy to \(\varPi_2^p\) and \(\varSigma_2^p\) in the famous polynomial hierarchy, we study the complexity classes \(\forall\exists\mathbb{R}\) and \(\exists\forall\mathbb{R}\) with real variables. Our main interest is focused on the Area Universality problem, where we are given a plane graph \(G\), and ask if for each assignment of areas to the inner faces of \(G\) there is an area-realizing straight-line drawing of \(G\). We conjecture that the problem Area Universality is \(\forall\exists\mathbb{R}\)-complete and support this conjecture by a series of partial results, where we prove \(\exists\mathbb{R}\)- and \(\forall\exists\mathbb{R}\)-completeness of variants of Area Universality. To do so, we also introduce first tools to study \(\forall\exists\mathbb{R}\). Finally, we present geometric problems as candidates for \(\forall\exists\mathbb{R}\)-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.
For the entire collection see [Zbl 1398.68016].