Exact Algorithms for Linear Programming over Algebraic Extensions

Abstract. We study the computational complexity of linear programs with coefficients that are real algebraic numbers under a Turing machine model of computation. After reviewing a method for exact representation of algebraic numbers under the Turing model, we show that the fundamental tasks of comparison and arithmetic can be performed in polynomial time. Our technique for establishing polynomial-time algorithms for comparison and arithmetic is distinct from the usual resultant-based approaches, and has the advantage that it provides a natural framework for analysis of the complexity of computational tasks, such as Gaussian elimination, that involve a sequence of arithmetic operations. Our main contribution is to show that a variant of the ellipsoid method can be used to solve linear programming in time polynomial in the encoding size of the problem coefficients and the degree of any algebraic extension that contains those coefficients.     

Polynomial algorithms for linear programming over the algebraic numbers

We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a rational-number problem. We also view the coefficients of a linear program as members of a finite algebraic extension of the rational numbers. The degree of this extension is an upper bound on the degree of any algebraic number that can occur during the course of the algorithm, and in this sense can be viewed as a supplementary measure of problem dimension. Working under an arithmetic model of computation, and making use of a tool for obtaining upper and lower bounds on polynomial functions of algebraic numbers, we derive an algorithm based on the ellipsoid method that runs in time bounded by a polynomial in the dimension, degree, and size of the linear program. Similar results hold under a rational number model of computation, given a suitable binary encoding of the problem input.This research was founded by the National Science Foundation under Grant DMS88-10192.     

Counting Irreducible Components of Complex Algebraic Varieties

We present an algorithm for counting the irreducible components of a complex algebraic variety defined by a fixed number of polynomials encoded as straight-line programs (slps). It runs in polynomial time in the Blum–Shub–Smale (BSS) model and in randomized parallel polylogarithmic time in the Turing model, both measured in the lengths and degrees of the slps. Our algorithm is obtained from an explicit version of Bertini’s theorem. For its analysis we further develop a general complexity theoretic framework appropriate for algorithms in algebraic geometry.     

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata

We investigate time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff's “Jumping Automata for Graphs.” Our strongest tradeoff is a quadratic lower bound on the product of time and space for graph traversal. For example, achieving linear time requires linear space, implying that depth-first search is optimal. Since our bound in fact applies to nondeterministic algorithms fornonconnectivity, it also implies that closure under complementation of nondeterministic space-bounded complexity classes is achieved only at the expense of increased time. To demonstrate that these structured models are realistic, we also investigate their power. In addition to admitting well known algorithms such as depth-first search and random walk, we show that one simple variant of this model is nearly as powerful as a Turing machine. Specifically, for general undirected graph problems, it can simulate a Turing machine with only a constant factor increase in space and a polynomial factor increase in time.     

Computational complexity via programming languages: constant factors do matter

The purpose of this work is to promote a programming-language approach to studying computability and complexity, with an emphasis on time complexity. The essence of the approach is: a programming language, with semantics and complexity measure, can serve as a computational model that has several advantages over the currently popular models and in particular the Turing machine. An obvious advantage is a stronger relevance to the practice of programming. In this paper we demonstrate other advantages: certain proofs and constructions that are hard to do precisely and clearly with Turing machines become clearer and easier in our approach, and sometimes lead to finer results. In particular, we prove several time hierarchy theorems, for deterministic and non-deterministic time complexity which show that, in contrast with Turing machines, constant factors do matter in this framework. This feature, too, brings the theory closer to practical considerations. The above result suggests that this framework may be appropriate for studying low complexity classes, such as linear time. As an example we give a problem complete for non-deterministic\/ linear time under deterministic linear-time reductions. Finally, we consider some extensions and modifications of our programming language and their effect on time complexity results. Received: 26 October 1998 / 9 June 2000     

The Complexity of Counting Problems in Equational Matching

We introduce a class of counting problems that arise naturally in equational matching and investigate their computational complexity. If E is an equational theory, then #E-Matching is the problem of counting the number of most general E-matchers of two given terms. #E-Matching is a well-defined algorithmic problem for every finitary equational theory. Moreover, it captures more accurately the computational difficulties associated with finding minimal complete sets of E-matchers than the corresponding decision problem for E-matching does.In 1979, L. Valiant developed a computational model for measuring the complexity of counting problems and demonstrated the existence of #P-complete problems, i.e., counting problems that are complete for counting non-deterministic Turing machines of polynomial-time complexity. Using the theory of #P-completeness, we analyze the computational complexity of #E-matching for several important equational theories E. We establish that if E is one of the equational theories A, C, AC, I, U, ACI, Set, ACU, or ACIU, then #E-Matching is a #P-complete problem. We also show that there are equational theories, such as the restriction of AC-matching to linear terms, for which the underlying decision matching problem is solvable in polynomial time, while the associated counting matching problem is #P-complete.     

Observations on the complexity of regular expression problems

Several observations are presented on the computational complexity of regular expression problems. The equivalence and containment problems are shown to require more than linear time on any multiple tape deterministic Turing machine. The complexity of the equivalence and containment problems is shown to be “essentially” independent of the structure of the languages represented. Subclasses of the regular grammars, that generate all regular sets but for which equivalence and containment are provably decidable deterministically in polynomial time, are also presented. As corollaries several program scheme problems studied in the literature are shown to be decidable deterministically in polynomial time.     

Minimal pairs of polynomial degrees with subexponential complexity

The goal of extending work on relative polynomial time computability from computations relative to sets of natural numbers to computations relative to arbitrary functions of natural numbers is discussed. The principal techniques used to prove that the honest subrecursive classes are a lattice are then used to construct a minimal pair of polynomial degrees with subexponential complexity; that is two sets computable by Turing machines in subexponential time but not in polynomial time are constructed such that any set computable from both in polynomial time can be computed directly in polynomial time.     

Symbolic and Numeric Methods for Exploiting Structure in Constructing Resultant Matrices

Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear algebra. Sparse elimination theory has introduced the sparse (or toric) resultant, which takes into account the sparse structure of the polynomials. The construction of sparse resultant, or Newton, matrices is the critical step in the computation of the multivariate resultant and the solution of a nonlinear system. We reveal and exploit the quasi-Toeplitz structure of the Newton matrix, thus decreasing the time complexity of constructing such matrices by roughly one order of magnitude to achieve quasi-quadratic complexity in the matrix dimension. The space complexity is also decreased analogously. These results imply similar improvements in the complexity of computing the resultant polynomial itself and of solving zero-dimensional systems. Our approach relies on fast vector-by-matrix multiplication and uses the following two methods as building blocks. First, a fast and numerically stable method for determining the rank of rectangular matrices, which works exclusively over floating point arithmetic. Second, exact polynomial arithmetic algorithms that improve upon the complexity of polynomial multiplication under our model of sparseness, offering bounds linear in the number of variables and the number of non-zero terms.     

Binary trees as a computational framework

We present a new set of algorithms for performing arithmetic computations on the set of natural numbers, represented as ordered rooted binary trees. We show formally that these algorithms are correct and discuss their time and space complexity in comparison to traditional arithmetic operations on bitstrings.Our binary tree algorithms follow the structure of a simple type language, similar to that of Gödel's System T.Generic implementations using Haskell's type class mechanism are shared between instances shown to be isomorphic to the set of natural numbers. This representation independence is illustrated by instantiating our computational framework to the language of balanced parenthesis languages.The self-contained source code of the paper is available at http://logic.cse.unt.edu/tarau/research/2012/jtypes.hs.     

Dead beat controllability of polynomial systems: symboliccomputation approaches

State and output dead beat controllability tests for a very large class of polynomial systems with rational coefficients may be based on the quantifier elimination by partial cylindrical algebraic decomposition (QEPCAD) symbolic computation program. The method is unified for a very large class of systems and can handle one- or two-sided control constraints. Families of minimum time state/output dead beat controllers are obtained. The computational complexity of the test is prohibitive for general polynomial systems, but by constraining the structure of the system we may beat the curse of complexity. A computationally less expensive algebraic test for output dead beat controllability for a class of odd polynomial systems is presented. Necessary and sufficient conditions are given. They are still very difficult to check. Therefore, a number of easier-to-check sufficient conditions are also provided. The latter are based on the Grobner basis method and QEPCAD. It is shown on a subclass of odd polynomial systems how it is possible to further reduce the computational complexity by exploiting the structure of the system     

Computing the Isolated Roots by Matrix Methods

Two main approaches are used, nowadays, to compute the roots of a zero-dimensional polynomial system. The first one involves Gröbner basis computation, and applies to any zero-dimensional system. But, it is performed withexact arithmetic and, usually, large numbers appear during the computation. The other approach is based on resultant formulations and can be performed with floating point arithmetic. However, it applies only to generic situations, leading to singular problems in several systems coming from robotics and computational vision, for instance.In this paper, reinvestigating the resultant approach from the linear algebra point of view, we handle the problem of genericity and present a new algorithm for computing the isolated roots of an algebraic variety, not necessarily of dimension zero. We analyse two types of resultant formulations, transform them into eigenvector problems, and describe special linear algebra operations on the matrix pencils in order to reduce the root computation to a non-singular eigenvector problem. This new algorithm, based on pencil decompositions, has a good complexity even in the non-generic situations and can be executed with floating point arithmetic.     

On the complexity of nonuniform wavelength-based machine

The wavelength-based machine, or simply w-machine, is an optical computational model, which is designed based on simultaneous movement of several wavelengths in a single light ray, and simultaneous effect of simple optical devices on them. In this paper, we investigate nonuniform complexity classes of w-machine, based on three complexity measures, namely, size, time, and word length. We show that the class of languages which can be generated by constant size nonuniform w-machines contain infinitely many Turing undecidable languages. Also, we show that polynomial size nonuniform w-machines generate all NP languages, and every NP-hard language requires at least polynomial time and polynomial size nonuniform w-machines to be generated. We prove that the class of languages which can be generated by polynomial size nonuniform w-machines is equal to NP/poly, and almost all languages require exponential size and polynomial time nonuniform w-machines to be generated.     

Small networks of polarized splicing processors are universal

In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set \(\{-1,0,1\}\) as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation.     

On a Refined Analysis of Some Problems in Interval Arithmetic Using Real Number Complexity Theory

We study some problems in interval arithmetic treated in Kreinovich et al. [13]. First, we consider the best linear approximation of a quadratic interval function. Whereas this problem (as decision problem) is known to be NP-hard in the Turing model, we analyze its complexity in the real number model and the analogous class NP . Our results substantiate that most likely it does not any longer capture the difficulty of NP in such a real number setting. More precisely, we give upper complexity bounds for the approximation problem for interval functions by locating it in (a real analogue of). This result allows several conclusions: the problem is not (any more) NP -hard under so called weak polynomial time reductions and likely not to be NP -hard under (full) polynomial time reductions; for fixed dimension the problem is polynomial time solvable; this extends the results in Koshelev et al. [12] and answers a question left open in [13].We also study several versions of interval linear systems and show similar results as for the approximation problem.Our methods combine structural complexity theory with issues from semi-infinite optimization theory.     

Interval Arithmetic in Cylindrical Algebraic Decomposition

Cylindrical algebraic decomposition requires many very time consuming operations, including resultant computation, polynomial factorization, algebraic polynomial gcd computation and polynomial real root isolation. We show how the time for algebraic polynomial real root isolation can be greatly reduced by using interval arithmetic instead of exact computation. This substantially reduces the overall time for cylindrical algebraic decomposition.     

Membrane computing and complexity theory: A characterization of PSPACE

A P system is a natural computing model inspired by information processing in cells and cellular membranes. We show that confluent P systems with active membranes solve in polynomial time exactly the class of problems PSPACE. Consequently, these P systems prove to be equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. Similar results were achieved also with other models of natural computation, such as DNA computing or genetic algorithms. Our result, together with the previous observations, suggests that the class PSPACE provides a tight upper bound on the computational potential of biological information processing models.     

Theories with self-application and computational complexity

Applicative theories form the basis of Feferman’s systems of explicit mathematics, which have been introduced in the 1970s. In an applicative universe, all individuals may be thought of as operations, which can freely be applied to each other: self-application is meaningful, but not necessarily total. It has turned out that theories with self-application provide a natural setting for studying notions of abstract computability, especially from a proof-theoretic perspective. This paper is concerned with the study of (unramified) bounded applicative theories which have a strong relationship to classes of computational complexity. We propose new applicative systems whose provably total functions coincide with the functions computable in polynomial time, polynomial space, polynomial time and linear space, as well as linear space. Our theories can be regarded as applicative analogues of traditional systems of bounded arithmetic. We are also interested in higher-type features of our systems; in particular, it is shown that Cook and Urquhart’s system is directly contained in a natural applicative theory of polynomial strength.     

A New Characterization of NP, P, and PSPACE with Accepting Hybrid Networks of Evolutionary Processors

We consider three complexity classes defined on Accepting Hybrid Networks of Evolutionary Processors (AHNEP) and compare them with the classical complexity classes defined on the standard computing model of Turing machine. By definition, AHNEPs are deterministic. We prove that the classical complexity class NP equals the family of languages decided by AHNEPs in polynomial time. A language is in P if and only if it is decided by an AHNEP in polynomial time and space. We also show that PSPACE equals the family of languages decided by AHNEPs in polynomial length.     

Complexity Theory and Genetics: The Computational Power of Crossing Over

We study the computational power of systems where information is stored in independent strings and each computational step consists of exchanging information between randomly chosen pairs. To this end we introduce a population genetics model in which the operators of selection and inheritance are effectively computable (in polynomial time on probabilistic Turing machines). We show that such systems are as powerful as the usual models of parallel computations, namely they can simulate polynomial space computations in polynomially many steps. We also show that the model has the same power if the recombination rules for strings are very simple (context sensitive crossing over).