Feasible Real Random Access Machines

We present a modified real RAM model which is equipped with the usual discrete and real-valued arithmetic operations and with a finite precision test <_kwhich allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). Furthermore, ourfeasible RAMhas an extended semantics which allows approximative computations. Using a logarithmic complexity measure we prove that all functions computable on a RAM in time (t) can be computed on a Turing machine in time (t²·log(t)·log log(t)). Vice versa all functions computable on a Turing machine in time (t) are computable on a RAM in time (t). Thus, our real RAM model does not only express exactly the computational power of Turing machines on real numbers (in the sense of Grzegorczyk), but it also yields a high-level tool for realistic time complexity estimations on real numbers.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

On the range maximum-sum segment query problem

The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers A[1…n] for subsequent queries of the form: “Given indices i, j, what is the index of the minimum value of A[i…j]?” This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: “Given indices i and j, what is the maximum-sum segment of A[i…j]?” We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper.     

Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

Approximation ofk-Monotone Functions

It is shown that an algebraic polynomial of degree k−1 which interpolates ak-monotone functionfatkpoints, sufficiently approximates it, even if the points of interpolation are close to each other. It is well known that this result is not true in general for non-k-monotone functions. As an application, we prove a (positive) result on simultaneous approximation of ak-monotone function and its derivatives inL_p, 0<p<1, metric, and also show that the rate of the best algebraic approximation ofk-monotone functions (with bounded (k−2)nd derivatives inL_p, 1<p<∞, iso(n^−k/p).     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Transfer Principle in the Real Plane from Nonsingular Algebraic Curves to Polynomial Vector Fields

For every nonsingular algebraic curve C of degree m in the real plane a polynomial vector field of degree 2m–1 is constructed, which has exactly the ovals of C as attracting limit cycles. Therefore, every progress on the algebraic part of Hilbert's 16th problem automatically yields progress on its dynamical part.     

δ-Uniform BSS Machines

Aδ-uniform BSS machine is a standard BSS machine which does not rely on exact equality tests. We prove that, for any real closed archimedean fieldR, a set isδ-uniformly semi-decidable iff it is open and semi-decidable by a BSS machine which is locally time bounded; we also prove that the local time bound condition is nontrivial. This entails a number of results about BSS machines, in particular the existence of decidable sets whose interior (closure) is not even semi-decidable without adding constants. Finally, we show that the sets semi-decidable by Turing machines are the sets semi-decidable byδ-uniform machines with coefficients inQorT, the field of Turing computable numbers.     

On Dynamic Algorithms for Algebraic Problems

In this paper, we examine the problem of incrementally evaluating algebraic functions. In particular, iff(x₁,x₂,…,x_n) = (y₁, y₂,…,y_m) is an algebraic problem, we consider answering on-line requests of the form “change inputx_ito valuev” or “what is the value of outputy_j?” We first present lower bounds for some simply stated algebraic problems such as multipoint polynomial evaluation, polynomial reciprocal, and extended polynomial GCD, proving an Ω(n) lower bound for the incremental evaluation of these functions. In addition, we prove two time-space trade-off theorems that apply to incremental algorithms for almost all algebraic functions. We then derive several general-purpose algorithm design techniques and apply them to several fundamental algebraic problems. For example, we give antime per request algorithm for incremental DFT. We also present a design technique for serving incremental requests using a parallel machine, giving a choice of either optimal work with respect to the sequential incremental algorithm or superfast algorithms withO(log log n) time per request with a sublinear number of processors.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem

Toda (in SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines in Bull. Am. Math. Soc. (NS) 21(1): 1–46, 1989) has been missing so far. In this paper we formulate and prove a real analogue of Toda’s theorem. Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques, we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry: the problem of deciding sentences in the first-order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result may be of independent interest to researchers in algorithmic semi-algebraic geometry.     

Ordinal machines and admissible recursion theory

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory.     

NOTE ON INVERSE PROBLEM WITH l∞ OBJECTIVE FUNCTION

In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.     

The 16th Hilbert problem on algebraic limit cycles

For real planar polynomial differential systems there appeared a simple version of the 16th Hilbert problem on algebraic limit cycles: Is there an upper bound on the number of algebraic limit cycles of all polynomial vector fields of degree m? In [J. Llibre, R. Ramírez, N. Sadovskaia, On the 16th Hilbert problem for algebraic limit cycles, J. Differential Equations 248 (2010) 1401-1409] Llibre, Ramírez and Sadovskaia solved the problem, providing an exact upper bound, in the case of invariant algebraic curves generic for the vector fields, and they posed the following conjecture: Is1+(m−1)(m−2)/2the maximal number of algebraic limit cycles that a polynomial vector field of degree m can have?In this paper we will prove this conjecture for planar polynomial vector fields having only nodal invariant algebraic curves. This result includes the Llibre et al.?s as a special one. For the polynomial vector fields having only non-dicritical invariant algebraic curves we answer the simple version of the 16th Hilbert problem.     

Personal Reminiscences of the Birth of Algebraic K-theory

These informal reminiscences, presented at the ICTP 2002 Conference on algebraic K-theory, recount the trajectory in the author's early research, from work on the Serre Conjecture (on projective modules over polynomial algebras), via ideas from algebraic geometry and topology, to the ideas and constructions that eventually contributed to the founding of algebraic K-theory. The solution of the Congruence Subgroup Problem is presented as a pivotal event.     

Minimum Color Sum of Bipartite Graphs

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn^{1 − ε}, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.     

An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths

In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v≠s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v≠s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem.