Computational complexity of real functions

Recursive analysis, the theory of computation of functions on real numbers, has been studied from various aspects. We investigate the computational complexity of real functions using the methods of recursive function theory. Partial recursive real functions are defined and their domains are characterized as the recursively open sets. We define the time complexity of recursive real continuous functions and show that the time complexity and the modulus of uniform continuity of a function are closely related. We study the complexity of the roots and the differentiability of polynomial time computable real functions. In particular, a polynomial time computable real function may have a root of arbitrarily high complexity and may be nowhere differentiable. The concepts of the space complexity and nondeterministic computation are used to study the complexity of the integrals and the maximum values of real functions. These problems are shown to be related to the “P=?NP” and the “P=?PSPACE” questions.     

A recursive second order initial algebra specification of primitive recursion

Theoretical results on the scope and limits of first order algebraic specifications can be used to show that certain natural algebras have no recursively enumerable equational specification under first order initial algebra semantics. A well known example is the algebraP of primitive recursive functions over the natural numbers. In this paper we show thatP has a recursive equational specification under second order initial algebra semantics. It follows that higher order initial algebra specifications are strictly more powerful than first order initial algebra specifications.     

Beyond Recursive Real Functions

All recursive real functions are continuous; in fact all theB-recursive real functions are continuous for any oracleB, simply because Turing machines computing them are finite objects. But simple discontinuous functions such as step functions have to be in some sense “easy” if they have recursive values and break points, although they are not computable by the usual definition. It seems unfair to label them noncomputable in the entire region just because of a few break points. In this paper, we investigate the properties of broader classes ofalmost everywhere recursive,weakly almost everywhere recursive, andrecursively approximablereal-valued functions, which capture these “easy” step functions and many other nonrecursive functions. Recursive versions of the classical Lusin and Egoroff Theorems are proved. We also characterize the property of the limit of a recursive sequence of functions and show that different notions of convergence (uniform, pointwise, or in measure) will result in different characterizations of the limiting function.     

The data type of spatial objects

A spatial object consists of data assigned to points in a space. Spatial objects, such as memory states and three dimensional graphical scenes, are diverse and ubiquitous in computing. We develop a general theory of spatial objects by modelling abstract data types of spatial objects as topological algebras of functions. One useful algebra is that of continuous functions, with operations derived from operations on space and data, and equipped with the compact-open topology. Terms are used as abstract syntax for defining spatial objects and conditional equational specifications are used for reasoning. We pose a completeness problem: Given a selection of operations on spatial objects, do the terms approximate all the spatial objects to arbitrary accuracy? We give some general methods for solving the problem and consider their application to spatial objects with real number attributes.     

On Discrete Minimax Problems in R Using Interval Arithmetic

Interval algorithms for bounding discrete minimax function values of problems in which the constituent minimax functions are continuously differentiable functions of one real variable in a bounded closed interval are presented, both with and without inequality constraints represented by continuously differentiable constraint functions.     

Some types of filters in BL algebras

In this paper we introduce some types of filters in a BL algebra A, and we state and prove some theorems which determine the relationship between these notions and other filters of a BL algebra, and by some examples we show that these notions are different. Also we consider some relations between these filters and quotient algebras that are constructed via these filters.     

A survey of recursive analysis and Moore’s notion of real computation

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore’s class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230–265, 1936), Grzegorczyk (Fundam Math 42:168–202, 1955), and Lacombe (Compt Rend l’Acad Sci Paris 241:151–153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore’s class and the relationships between them.     

A parallel quasi-Newton algorithm for unconstrained optimization

In this paper, we present an asynchronous parallel quasi-Newton method. We assume that we havep+q processors, which are divided into two groups, the two groups execute in an asynchronous parallel fashion. If we assume that the objective function is twice continuously differentiable and uniformly convex, we discuss the global and superlinear convergence of the parallel BFGS method. Finally we show numerical results of this algorithm.     

Statistical Zero Knowledge and quantum one-way functions

One-way functions are a fundamental notion in cryptography, since they are the necessary condition for the existence of secure encryption schemes. Most examples of such functions, including Factoring, Discrete Logarithm or the RSA function, however, can be inverted with the help of a quantum computer. Hence, it is very important to study the possibility of quantum one-way functions, i.e. functions which are easily computable by a classical algorithm but are hard to invert even by a quantum adversary. In this paper, we provide a set of problems that are good candidates for quantum one-way functions. These problems include Graph Non-Isomorphism, Approximate Closest Lattice Vector and Group Non-Membership. More generally, we show that any hard instance of Circuit Quantum Sampling gives rise to a quantum one-way function. By the work of Aharonov and Ta-Shma [D. Aharonov, A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, in: Proceedings of STOC02 — Symposium on the Theory of Computing, 2001], this implies that any language in Statistical Zero Knowledge which is hard-on-average for quantum computers leads to a quantum one-way function. Moreover, extending the result of Impagliazzo and Luby [R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography, in: Proceedings of FOCS89 — Symposium on Foundations of Computer Science, 1989] to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions.     

The complexity of constraint satisfaction problems for small relation algebras

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete.     

Konvergenz von quadratischen Interpolations- und Flächenabgleichssplines

The purpose of this paper is to show that for continuous functions the related quadratic splines converge without any assumption on the spline grid. The points of the interpolatory grid can be chosen between the corresponding points of the spline grid with a division ratio from \(\frac{{\sqrt 2 }}{2}\) to \(1 - \frac{{\sqrt 2 }}{2}\) . In the case of continuously differentiable functions the division ratio can even be taken between 0 and 1; in addition, the order of convergence is increased. For twice differentiable functions the full order of convergence is obtained. Analogous results about the convergence of histo splines are proved.     

The closure properties on real numbers under limits and computable operators

In effective analysis, various classes of real numbers are discussed. For example, the classes of computable, semi-computable, weakly computable, recursively approximable real numbers, etc. All these classes correspond to some kind of (weak) computability of the real numbers. In this paper we discuss mathematical closure properties of these classes under the limit, effective limit and computable function. Among others, we show that the class of weakly computable real numbers is not closed under effective limit and partial computable functions while the class of recursively approximable real numbers is closed under effective limit and partial computable functions.     

Approximate well-founded semantics, query answering and generalized normal logic programs over lattices

The management of imprecise information in logic programs becomes important whenever the real world information to be represented is of an imperfect nature and the classical crisp true, false approximation is not adequate. In this work, we consider normal logic programs over complete lattices, where computable truth combination functions may appear in the rule bodies to manipulate truth values and we will provide a top-down query answering procedure.     

Some Undecidable Problems on Approximability of NP Optimization Problems

'1IntroductionManydecisionproblemsareNPcompleteandtheirassociatedoptimizationproblemsareNPequivalent.ButtheseoptimizationproblemshaveverydifferentaPprokimabilities.Forexample,knapsackproblemhasapolynomial-timeapproki-mationscheme,whileTSPisnotconstall-aPprotimable,unlessP=NP.WhatmakesdifferenceamongNPoptimizationproblems(NPOPs)?In[3],KolaitisandThakurinvestigatedtheapprokimabilityofNPOPsbymeansofrepresentingNPOPswithfirst-orderselltences-TheyprovedthatifP/NP,thenitisanundecidable…     

Effectively given domains

A definition of the notion of an effectively given continuous cpo is provided. The importance of the notion lies in the fact that we can readily characterize the computable (partial) functions of arbitrary finite type over an effectively given domain. We show that the definition given here is closed under several important domain constructions, namely sum, product, function space, powerdomain and inverse limits (the last two in a restricted form); this permits recursive domain equations to be solved effectively.     

On the role of logical connectives for primality and functional completeness of algebras of logics

We consider certain finite universal algebras arising from algebraic semantics in implicational logics. They contain a binary operation → and two constants 0 and 1 satisfying the axioms 0→x=x→1=x→x=1 and 1→x=x valid in most implicational logics. We characterize the completeness (also called primality) of such algebras, i.e. the property that every finitary operation on their universe is a term operation of the algebra (in other words, it is a composition of the basic operations of the algebra). Using clone theory and the knowledge of maximal clones we describe completeness (functional completeness) in terms of nonpreservation of three types of specific relations. If → has a simple property and the algebra contains a binary operation ⊙ with a neutral element 1 and a unary operation ¬ satisfying ¬(1)=0 and ¬x=1 otherwise, the algebra is functionally complete.     

How Powerful Are Integer-Valued Martingales?

In the theory of algorithmic randomness, one of the central notions is that of computable randomness. An infinite binary sequence?X is computably random if no recursive martingale (strategy) can win an infinite amount of money by betting on the values of the bits of?X. In the classical model, the martingales considered are real-valued, that is, the bets made by the martingale can be arbitrary real numbers. In this paper, we investigate a more restricted model, where only integer-valued martingales are considered, and we study the class of random sequences induced by this model.     

0-homogeneous effect algebras

In the present paper, we introduce a proper superclass of homogeneous effect algebras. We call this superclass as 0-homogeneous effect algebras. We prove that in every 0-homogeneous effect algebra, the set of all sharp elements forms a subalgebra. Every chain-complete 0-homogeneous effect algebra is homogeneous.     

Global optimization with data perturbations

In previous publications algorithms by the author were described for solving the global nonlinear optimization problem for the unconstrained and the inequality constrained cases. The algorithms are applicable when the objective function is twice continuously differentiable and the constraints are continuously differentiable. They provide infallible bounds on the minimal value of the objective function and the point(s) at which it occurs.In this paper, we show these algorithms are equally applicable when the data is either exact or perturbed. In the latter case, it is assumed that perturbations can be described by specifying the coefficients in the objective and constraint functions as intervals. No changes in the programs are required to solve the perturbed case. Only the objective and constraint functions change to reflect the uncertainty in data. Numerical results are given.