Approximate decidability in euclidean spaces

We study concepts of decidability (recursivity) for subsets of Euclidean spaces ?^k within the framework of approximate computability (type two theory of effectivity). A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces.     

Feasible Operations and Applicative Theories Based on λη

We study a theory PTO(λη) of polynomial time computability on the type of binary strings (in the style of [6]), as embedded in full lambda calculus with total application and extensionality. We prove that the closed terms of (provable) type W → W are exactly the polynomial time operations. This answers a conjecture of Strahm [13].     

Enumeration problems for classes of self-similar graphs

We describe a general construction principle for a class of self-similar graphs. For various enumeration problems, we show that this construction leads to polynomial systems of recurrences and provide methods to solve these recurrences asymptotically. This is shown for different examples involving classical self-similar graphs such as the Sierpiński graphs. The enumeration problems we investigate include counting independent subsets, matchings and connected subsets.     

Effective embeddings into strong degree structures

We show that any partial order with a Σ₃ enumeration can be effectively embedded into any partial order obtained by imposing a strong reducibility such as ≤_tt on the c. e. sets. As a consequence, we obtain that the partial orders that result from imposing a strong reducibility on the sets in a level of the Ershov hiearchy below ω + 1 are co‐embeddable.     

Reducibility on families

A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical computability and on admissible sets: for example, describing index sets of families belonging to , generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc. *Supported by RFBR (project No. 05-01-00605) and by the Council for Grants (under RF President) and State Aid of Young Candidates of Science (grant MK-4314.2008.1). **Supported by RFBR (projects No. 08-01-00442 and 06-04002-DFGa), by the Council for Grants (under RF President) of Leading Scientific Schools (grant NSh-335.2008.1), and by the Russian Foundation for Support of Domestic Science. Translated from Algebra i Logika, Vol. 48, No. 1, pp. 31-53, January-February, 2009.     

Enumerating teams in first-order team logics

We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was recently introduced by Creignou et al. (Discret. Appl. Math. 2019). We show that the problem to enumerate all satisfying teams of a fixed formula in a given first-order structure is DelNP-complete for certain formulas of dependence logic and independence logic. For inclusion logic formulas, this problem is even in DelP. Furthermore, we study the variants of this problem where only maximal or minimal solutions, with respect to cardinality or inclusion, are considered. For the most part these share the same complexity as the original problem. One exception is the cardinality minimum-variant for inclusion logic, which is DelNP-complete, the other is the inclusion maximal-variant for dependence and independence logic, which is in Del⁺NP and DelNP-hard.     

On MODkP Counting Degrees

For a prime k, the embeddability of finite lattices are discussed for various kind of the MOD_kP degrees of recursive sets. In particular, all finite lattices are embeddable into the MOD_kP Turing degrees, whereas the non distributive lattice M₃ is embeddable into the MOD₂P many-one degrees but N₅ is not.     

Analytical properties of resource-bounded real functionals

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0, 1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.     

On centain decompositions of Gödel numberings

Summary We define certain decompositions of the functions that describe Gödel numberings of the partial recursive functions (Section 2). These decompositions reflect the way in which concrete Gödel numberings may be obtained from the known computability formalisms. We show that such decompositions exist for all partial recursive functions (Section 3). It turns out that there is an intimate connection between these decompositions and Blum's step counting functions which yields a suggestive interpretation of Blum's notion (Section 4). In terms of these decompositions we, finally, give an exact formulation for a basic problem in the theory of computability formalisms, which, on an intuitive level, would read as follows: Find conditions on the expressive power of one step in a given computability formalism such that all partial recursive functions can be represented within that formalism. We derive two theorems which may be regarded as a first step in a thorough study of this problem.     

Polynomial Time Uniform Word Problems

We have two polynomial time results for the uniform word problem for a quasivariety Q: (a) The uniform word problem for Q can be solved in polynomial time iff one can find a certain congruence on finite partial algebras in polynomial time. (b) Let Q* be the relational class determined by Q. If any universal Horn class between the universal closure S(Q*) and the weak embedding closure S?(Q*) of Q* is finitely axiomatizable then the uniform word problem for Q is solvable in polynomial time. This covers Skolem's 1920 solution to the uniform word problem for lattices and Evans' 1953 applications of the weak embeddability property for finite partial V algebras.     

Turing oracle machines, online computing, and three displacements in computability theory

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine (o-machine) and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form.A number of topics arose from Turing functionals including continuous functionals on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14.     

BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS

A hierarchy of functions with respect to their role as bounds in the Turing reducibility of functions is introduced and studied. This hierarchy leads to a certain notion of incompressibility of sets which is also investigated.     

Light affine lambda calculus and polynomial time strong normalization

Light Linear Logic (LLL) and Intuitionistic Light Affine Logic (ILAL) are logics that capture polynomial time computation. It is known that every polynomial time function can be represented by a proof of these logics via the proofs-as-programs correspondence. Furthermore, there is a reduction strategy which normalizes a given proof in polynomial time. Given the latter polynomial time “weak” normalization theorem, it is natural to ask whether a “strong” form of polynomial time normalization theorem holds or not. In this paper, we introduce an untyped term calculus, called Light Affine Lambda Calculus (λLA), which corresponds to ILAL. λLA is a bi-modal λ-calculus with certain constraints, endowed with very simple reduction rules. The main property of LALC is the polynomial time strong normalization: any reduction strategy normalizes a given λLA term in a polynomial number of reduction steps, and indeed in polynomial time. Since proofs of ILAL are structurally representable by terms of λLA, we conclude that the same holds for ILAL. This is a full version of the paper [21] presented at LICS 2001.     

Preventing redundant solutions in partial enumeration algorithms

Many algorithms for discrete problems use a variation of the tree-search enumeration technique as a basis for the algorithm. If a solution is the assignment of an attribute from a set ofm attributes to every variable in a set ofn variables, then redundant solutions can be generated if either the attributes or the variables contain some indistinguishable elements. A series of necessary and sufficient techniques are developed to eliminate the production of redundant solutions during enumeration. These techniques can be used to form the foundation of any partial enumeration algorithm where redundant solutions can be produced.     

Counting the number of independent sets in chordal graphs

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.     

Finding a Simple Polytope from Its Graph in Polynomial Time

We show that one can compute the combinatorial facets of a simple polytope from its graph in polynomial time. Our proof relies on a primal-dual characterization (by Joswig, Kaibel, and Körner in Israel J. Math. 129:109–118, 2002) and a linear program, with an exponential number of constraints, which can be used to construct the solution and can be solved in polynomial time. We show that this allows one to characterize the face lattice of the polytope, via a simple face recognition algorithm. In addition, we use this linear program to construct several interesting polynomial-time computable sets of graphs which may be of independent interest.     

c-Quasiminimal Enumeration Degrees

The notion of a C-quasiminimal set, with C an arbitrary subset of the naturals, was introduced by Sasso and presents a relativization of the well-known notion of quasiminimal set which was first constructed by Medvedev for proving the existence of nontotal enumeration degrees. In this article we study the local properties of the partially ordered set of the enumeration degrees containing C-quasiminimal sets. In particular, we prove for arbitrary enumeration degrees c and a that if c<a and a is a total e-degree then each at most countable partial order embeds isomorphically into the partially ordered set of c-quasiminimal e-degrees lying below a.     

On the Relation of Σ-Reducibility Between Admissible Sets

Reducibility on admissible sets is studied which is a stronger version of the usual -presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to -superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

Coloring linear orders with Rado's partial order

Let ?_R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order (a standard example of a wqo which is not a bqo). We show that ?_R has fairly high complexity with respect to Borel reducibility (e.g. if P is a Borel preorder, then P ≤_B ?_R), although its exact classification remains open. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)