Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial time e‐degrees as the equivalence classes under this reducibility and (...) investigate their structure on the recursive sets, showing in particular that the pe‐degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy. (shrink)

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...) assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

We define an applicative theoryCL 2 similar to combinatory logic which can be interpreted in classes of functions possessing an enumerating function. In contrast to the models of classical combinatory logic, it is not necessarily assumed that the enumerating function itself belongs to that function class. Thereby we get a variety of possible models including e. g. the classes of primitive recursive, recursive, elementary, polynomial-time comptable ofɛ 0-recursive functions.We show that inCL 2 a major part of the metatheory of (...) enumerated classes of functions can be developed. Namely, a kind of λ-abstraction can be defined and abstract versions of theS n m - and (Primitive) Recursion Theorems are proved. Thereby, a closer analysis of the phenomenon of the different recursion theorems is achieved.A theory closely related toCL 2 can be used to replace the applicative part of Feferman's theories for explicit mathematics. So this work can be seen as an answer to Feferman's question to formulate a theory for explicit mathematics in which operations can be interpreted as primitive recursive or even more feasible ones.Finally it is shown that the proof-theoretical strength of various theoreies for explicit mathematics is preserved when replacing the applicative part of the theories by our theory together with an operation for primitive recursion. (shrink)

We present a new manifestation of Gödel’s second incompleteness theorem and discuss its foundational significance, in particular with respect to Hilbert’s program. Specifically, we consider a proper extension of Peano arithmetic ( $\mathbf {PA}$ ) by a mathematically meaningful axiom scheme that consists of $\Sigma ^0_2$ -sentences. These sentences assert that each computably enumerable ( $\Sigma ^0_1$ -definable without parameters) property of finite binary trees has a finite basis. Since this fact entails the existence of polynomial time algorithms, it (...) is relevant for computer science. On a technical level, our axiom scheme is a variant of an independence result due to Harvey Friedman. At the same time, the meta-mathematical properties of our axiom scheme distinguish it from most known independence results: Due to its logical complexity, our axiom scheme does not add computational strength. The only known method to establish its independence relies on Gödel’s second incompleteness theorem. In contrast, Gödel’s theorem is not needed for typical examples of $\Pi ^0_2$ -independence (such as the Paris–Harrington principle), since computational strength provides an extensional invariant on the level of $\Pi ^0_2$ -sentences. (shrink)

Reverse Mathematics (RM) is a program in the foundations of mathematics where the aim is to find the minimal axioms needed to prove a given theorem of ordinary mathematics. Generally, the minimal axioms are equivalent to the theorem at hand, assuming a weak logical system called the base theory. Moreover, many theorems are either provable in the base theory or equivalent to one of four logical systems, together called the Big Five. For instance, the Weierstrass approximation theorem, i.e., that a (...) continuous function can be approximated uniformly by a sequence of polynomials, has been classified in RM as being equivalent to weak König’s lemma, the second Big Five system. In this paper, we study approximation theorems for discontinuous functions via Bernstein polynomials from the literature. We obtain many equivalences between the latter and weak König’s lemma. We also show that slight variations of these approximation theorems fall far outside of the Big Five but fit in the recently developed RM of new ‘big’ systems, namely the uncountability of ${\mathbb R}$, the enumeration principle for countable sets, the pigeon-hole principle for measure, and the Baire category theorem. (shrink)

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from small (...) time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

Machine generated contents note: 1. The Computability Concept;2. General Recursive Functions;3. Programs and Machines;4. Recursive Enumerability;5. Connections to Logic;6. Degrees of Unsolvability;7. Polynomial-Time Computability;Appendix: Mathspeak;Appendix: Countability;Appendix: Decadic Notation;.

For a ring R, Hilbert’s Tenth Problem $HTP$ is the set of polynomial equations over R, in several variables, with solutions in R. We view $HTP$ as an enumeration operator, mapping each set W of prime numbers to $HTP$, which is naturally viewed as a set of polynomials in $\mathbb {Z}[X_1,X_2,\ldots ]$. It is known that for almost all W, the jump $W'$ does not $1$ -reduce to $HTP$. In contrast, we show that every Turing degree contains a (...) set W for which such a $1$ -reduction does hold: these W are said to be HTP-complete. Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP$ can succeed uniformly on a set of measure $1$, and regarding the consequences for the boundary sets of the $HTP$ operator in case $\mathbb {Z}$ has an existential definition in $\mathbb {Q}$. (shrink)

Many proposals for logic-based formalisations of argumentation consider an argument as a pair (Φ,α), where the support Φ is understood as a minimal consistent subset of a given knowledge base which has to entail the claim α. In case the arguments are given in the full language of classical propositional logic reasoning in such frameworks becomes a computationally costly task. For instance, the problem of deciding whether there exists a support for a given claim has been shown to be -complete. (...) In order to better understand the sources of complexity (and to identify tractable fragments), we focus on arguments given over formulæ in which the allowed connectives are taken from certain sets of Boolean functions. We provide a complexity classification for four different decision problems (existence of a support, checking the validity of an argument, relevance and dispensability) with respect to all possible sets of Boolean functions. Moreover, we make use of a general schema to enumerate all arguments to show that certain restricted fragments permit polynomial delay. Finally, we give a classification also in terms of counting complexity. (shrink)

Call a (strictly increasing) sequence (rn) of natural numbers regular if it satisfies the following condition: rn+1/rn→θ∈R>1∪{∞} and, if θ is algebraic, then (rn) satisfies a linear recurrence relation whose characteristic polynomial is the minimal polynomial of θ. Our main result states that (Z,+,0,R) is superstable whenever R is enumerated by a regular sequence. We give two proofs of this result. One relies on a result of E. Casanovas and M. Ziegler and the other on a quantifier elimination (...) result. We also show that (Z,+,0,<,R) is NIP whenever R is enumerated by a regular sequence that is ultimately periodic modulo m for all m>1. (shrink)

An oracle A is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using A as an oracle, then it can be decided without an oracle in time $p(t(n))$ for some polynomial p. The existence of a set which is low-for-speed was first shown by Bayer and Slaman who constructed a non-computable computably enumerable set which is low-for-speed. In this paper we (...) answer a question previously raised by Bienvenu and Downey, who asked whether there is a minimal degree which is low-for-speed. The standard method of constructing a set of minimal degree via forcing is incompatible with making the set low-for-speed; but we are able to use an interesting new combination of forcing and full approximation to construct a set which is both of minimal degree and low-for-speed. (shrink)

We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher but which requires exponential resources to be learned given access only to a membership oracle. In general, we compare the families that can be learned with and without teachers and oracles for four measures of efficient learning.

We show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same "expressive power" and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomophy rings of Q.

Fix a weakly minimal (i.e. superstable U-rank 1) structure M. Let M∗ be an expansion by constants for an elementary substructure, and let A be an arbitrary subset of the universe M. We show that all formulas in the expansion (M∗,A) are equivalent to bounded formulas, and so (M,A) is stable (or NIP) if and only if the M-induced structure AM on A is stable (or NIP). We then restrict to the case that M is a pure abelian group with (...) a weakly minimal theory, and AM is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of (Z,+). Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form (M,A). Most notably, we show that if (G,+) is a weakly minimal additive subgroup of the algebraic numbers, A⊆G is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of A is a root of unity, then (G,+,B) is superstable for any B⊆A. (shrink)

Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz (...) random and ${\fancyscript{C}_{1} \nsubseteq \fancyscript{C}_{2}}$ are polynomial clones, then there is a B that is ${\fancyscript{C}_{1}}$ -reducible to A but not ${\fancyscript{C}_{2}}$ -reducible to A. This implies a generalization of a result first proved by Lachlan (Z Math Logik Grundlagen Math 11:17–44, 1965) for the case |X| = 2. We also show that the same result holds if Kurtz random is replaced by Kolmogorov–Loveland stochastic. (shrink)

A new proof style adequate for modal logics is defined from the polynomial ring calculus. The new semantics not only expresses truth conditions of modal formulas by means of polynomials, but also permits to perform deductions through polynomial handling. This paper also investigates relationships among the PRC here defined, the algebraic semantics for modal logics, equational logics, the Dijkstra???Scholten equational-proof style, and rewriting systems. The method proposed is throughly exemplified for S 5, and can be easily extended to (...) other modal logics. (shrink)

We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations Eλ and id. In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.

Harmony Search Algorithm (HSA) is an evolutionary algorithm which mimics the process of music improvisation to obtain a nice harmony. The algorithm has been successfully applied to solve optimization problems in different domains. A significant shortcoming of the algorithm is inadequate exploitation when trying to solve complex problems. The algorithm relies on three operators for performing improvisation: memory consideration, pitch adjustment, and random consideration. In order to improve algorithm efficiency, we use roulette wheel and tournament selection in memory consideration, replace (...) the pitch adjustment and random consideration with a modified polynomial mutation, and enhance the obtained new harmony with a modified β-hill climbing algorithm. Such modification can help to maintain the diversity and enhance the convergence speed of the modified HS algorithm. β-hill climbing is a recently introduced local search algorithm that is able to effectively solve different optimization problems. β-hill climbing is utilized in the modified HS algorithm as a local search technique to improve the generated solution by HS. Two algorithms are proposed: the first one is called PHSβ–HC and the second one is called Imp. PHSβ–HC. The two algorithms are evaluated using 13 global optimization classical benchmark function with various ranges and complexities. The proposed algorithms are compared against five other HSA using the same test functions. Using Friedman test, the two proposed algorithms ranked 2nd (Imp. PHSβ–HC) and 3rd (PHSβ–HC). Furthermore, the two proposed algorithms are compared against four versions of particle swarm optimization (PSO). The results show that the proposed PHSβ–HC algorithm generates the best results for three test functions. In addition, the proposed Imp. PHSβ–HC algorithm is able to overcome the other algorithms for two test functions. Finally, the two proposed algorithms are compared with four variations of differential evolution (DE). The proposed PHSβ–HC algorithm produces the best results for three test functions, and the proposed Imp. PHSβ–HC algorithm outperforms the other algorithms for two test functions. In a nutshell, the two modified HSA are considered as an efficient extension to HSA which can be used to solve several optimization applications in the future. (shrink)

if and only if for every W in V, W is independent of the set of all its non-descendants conditional on the set of its parents. One natural question that arises with respect to DAGs is when two DAGs are “statistically equivalent”. One interesting sense of “statistical equivalence” is “d-separation equivalence” (explained in more detail below.) In the case of DAGs, d-separation equivalence is also corresponds to a variety of other natural senses of statistical equivalence (such as representing the same (...) set of distributions). Theorems characterizing d-separation equivalence for directed acyclic graphs and that can be used as the basis for polynomial time algorithms for checking d-separation equivalence were provided by Verma and Pearl (1990), and Frydenberg (1990). The question we will examine is how to extend these results to cases where a DAG may have latent (unmeasured) variables or selection bias (i.e. some of the variables in the DAG have been conditioned on.) D-separation equivalence is of interest in part because there are algorithms for constructing DAGs with latent variables and selection bias that are based on observed conditional independence relations. For this class of algorithms, it is impossible to determine which of two d-separation equivalent causal structures generated a given probability distribution, given only the set of conditional independence and dependence relations true of the observed distribution. We will describe a polynomial (in the number of vertices) time algorithm for determining when two DAGs which may have latent variables or selection bias are d-separation equivalent. (shrink)

We give a counterexample to the claim that every provably total function of Basic Arithmetic is a polynomially bounded primitive recursive function.

Representations of the fingers are embodied in our cognition and influence performance in enumeration tasks. Among deaf signers, the fingers also serve as a tool for communication in sign language. Previous studies in normal hearing (NH) participants showed effects of embodiment (i.e., embodied numerosity) on tactile enumeration using the fingers of one hand. In this research, we examined the influence of extensive visuo‐manual use on tactile enumeration among the deaf. We carried out four enumeration task experiments, (...) using 1–5 stimuli, on a profoundly deaf group (n = 16) and a matching NH group (n = 15): (a) tactile enumeration using one hand, (b) tactile enumeration using two hands, (c) visual enumeration of finger signs, and (d) visual enumeration of dots. In the tactile tasks, we found salient embodied effects in the deaf group compared to the NH group. In the visual enumeration of finger signs task, we controlled the meanings of the stimuli presentation type (e.g., finger‐counting habit, fingerspelled letters, both or neither). Interestingly, when comparing fingerspelled letters to neutrals (i.e., not letters or numerical finger‐counting signs), an inhibition pattern was observed among the deaf. The findings uncover the influence of rich visuo‐manual experiences and language on embodied representations. In addition, we propose that these influences can partially account for the lag in mathematical competencies in the deaf compared to NH peers. Lastly, we further discuss how our findings support a contemporary model for mental numerical representations and finger‐counting habits. (shrink)

We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy . The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai.

Motivated by results on interactive proof systems we investigate an ∃-∀hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every class of this hierarchy coincides with one of the following Classes: ∑math image, Πmath image , PSPACE, ∑math image or Πmath image . This improves previous results by Orponen [6] and allows interesting comparisons with the above (...) mentioned results on inter-active proof systems. (shrink)

This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus (...) counting. We show that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting. (shrink)

It is shown in this article that the two sides of an equation in the medieval Arabic algebra are aggregations of the algebraic “numbers” (powers) with no operations present. Unlike an expression such as our 3x + 4, the Arabic polynomial “three things and four dirhams” is merely a collection of seven objects of two different types. Ideally, the two sides of an equation were polynomials so the Arabic algebraists preferred to work out all operations of the enunciation to (...) a problem before stating an equation. Some difficult problems which involve square roots and divisions cannot be handled nicely by this basic method, so we do find square roots of polynomials and expressions of the form “A divided by B” in some equations. But rather than initiate a reconsideration of the notion of equation, these developments were used only for particularly complex problems. Also, the algebraic notation practiced in the Maghreb in the later middle ages was developed with the “aggregations” interpretation in mind, so it had no noticeable impact on the concept of polynomial. Arabic algebraists continued to solve problems by working operations before setting up an equation to the end of the medieval period. (shrink)

It is shown that the feasibly constructive arithmetic theory IPV does not prove LMIN, unless the polynomial hierarchy CPV-provably collapses. It is proved that PV plus LMIN intuitionistically proves PIND. It is observed that PV + PIND does not intuitionistically prove NPB, a scheme which states that the extended Frege systems are not polynomially bounded.

We have two polynomial time results for the uniform word problem for a quasivariety Q: 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. Let Q* be the relational class determined by Q. If any universal Horn class between the universal closure S and the weak embedding closure S̄ 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. (shrink)

A polynomially bounded recursive realizability, in which the recursive functions used in Kleene's realizability are restricted to polynomially bounded functions, is introduced. It is used to show that provably total functions of Ruitenburg's Basic Arithmetic are polynomially bounded (primitive) recursive functions. This sharpens our earlier result where those functions were proved to be primitive recursive. Also a polynomially bounded schema of Church's Thesis is shown to be polynomially bounded realizable. So the schema is consistent with Basic Arithmetic, whereas it is (...) inconsistent with Heyting Arithmetic. (shrink)

The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, the (...) [Formula: see text]-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new [Formula: see text]-principle that is conjectured to separate [Formula: see text] and [Formula: see text]. (shrink)

We introduce the class PIO of functions computable in time that is polynomial in max{the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings.

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...) We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions. (shrink)

We consider Choiceless Polynomial Time , a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting from image. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the (...) rank of sets used, even in image, an extension of image with counting. (shrink)

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

For each k > 0 we construct an algebraic structure over which the polynomial hierarchy collapses at level k. We also find an algebraic structure over which the polynomial hierarchy does not collapse.

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.

A closed λ-term E is called an enumerator if M ε /gL/dg /gTn ε N E/drn/dl = β M. Here Λ° is the set of closed λ-terms, N is the set of natural numbers and the /drn/dl are the Church numerals λfx./tfnx. Such an E is called reducing if moreover M ε /gL/dg /gTn ε N E/drn/dl /a/gb M. In 1983 I conjectured that every enumerator is reducing. An ingenious recursion theoretic proof of this conjecture by Statman is presented in (...) Barendregt . The proof is not intuitionistically valid, however. Dirk van Dalen has encouraged me to find intuitionistic proofs whenever possible. In the lambda calculus this is usually not difficult. In this paper an intuitionistic version of Statmans proof will be given. It took me somewhat longer to find it than in other cases. (shrink)

Sierpinski networks are networks of fractal nature having several applications in computer science, music, chemistry, and mathematics. These networks are commonly used in chaos, fractals, recursive sequences, and complex systems. In this article, we compute various connectivity polynomials such as M -polynomial, Zagreb polynomials, and forgotten polynomial of generalized Sierpinski networks S k n and recover some well-known degree-based topological indices from these. We also compute the most general Zagreb index known as α, β -Zagreb index and several (...) other general indices of similar nature for this network. Our results are the natural generalizations of already available results for particular classes of such type of networks. (shrink)

We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than (...) s-reducibility, we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (shrink)

The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is hoped will (...) make this volume an invaluable resource for specialists and non-specialists alike. (shrink)

Two-player, zero-sum, non-cooperative, blindfold games in extensive form with incomplete information are considered in this paper. Any information about past moves which players played is stored in a database, and each player can access the database. A polynomial game is a game in which, at each step, all players withdraw at most a polynomial amount of previous information from the database. We show resource-bounded determinacy of some kinds of finite, zero-sum, polynomial games whose pay-off sets are computable (...) by non-deterministic polynomial-time function-oracle Turing machines. We call a pay-off set -determined if, for any polynomial game G associated with the given pay-off set, either player has a winning strategy which is in for any subgames of G. We show that there exists an FP-strongly-determined pay-off set which is computed by an exponential-time oracle Turing machine, where FP is the set of polynomial-time computable functions. We also discuss several relationships between the determinacy of polynomial games and recursion-theoretic properties for the classes co-NP and co-NEXP. We show that the polynomial version of the axiom of choice holds under some assumption of polynomial determinacy for a pay-off set which is polynomial-time computable with parallel queries. This principle of choice implies that co-NP has the separation property. (shrink)

Polynomizing is a term that intends to describe the uses of polynomial-like representations as a reasoning strategy and as a tool for scientific heuristics. I show how proof-theory and semantics for classical and several non-classical logics can be approached from this perspective, and discuss the assessment of this prospect, in particular to recover certain ideas of George Boole in unifying logic, algebra and the differential calculus.

We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤be, which is a natural extension of s-reducibility ≤s. We show that ≤s, ≤be, and enumeration reducibility do not coincide on the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} –sets, and the structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that the (...) first order theory of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper (Z Math Logik Grundlag Math 33:537–560, 1987). (shrink)

We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S21 exists in which NP is not in the second level of the linear hierarchy; and that a model of S21 exists in which the polynomial hierarchy collapses to the linear hierarchy. Our methods are model-theoretic. We use the assumption about factoring to get a model in which (...) the weak pigeonhole principle fails in a certain way, and then work with this failure to obtain our results. As a corollary of one of the proofs, we also show that in S21 the failure of WPHP (for Σb1 definable relations) implies that the strict version of PH does not collapse to a finite level. (shrink)

Some properties and an algorithm for solving systems of multivariate polynomial equations over finite fields are presented. It is then shown how formulas of propositional logics can be translated into polynomials over finite fields in such a way that several logic problems are expressed in terms of algebraic problems. Consequently, algebraic properties and algorithms can be used to solve the algebraically-represented logic problems. The methods described herein combine and generalise those of various previous works.

We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.

In this paper we study (self)-applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on W = {0, 1} * are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.

A polynomial time ultrapower is a structure given by the set of polynomial time computable functions modulo some ultrafilter. They model the universal theory \ of all polynomial time functions. Generalizing a theorem of Hirschfeld :111–126, 1975), we show that every countable model of \ is isomorphic to an existentially closed substructure of a polynomial time ultrapower. Moreover, one can take a substructure of a special form, namely a limit polynomial time ultrapower in the classical (...) sense of Keisler Ultrafilters across mathematics, contemporary mathematics vol 530, pp 163–179. AMS, New York, 1963). Using a polynomial time ultrapower over a nonstandard Herbrand saturated model of \ we show that \ is consistent with a formal statement of a polynomial size circuit lower bound for a polynomial time computable function. This improves upon a recent result of Krajíček and Oliveira, 2017). (shrink)