A set A is m-reducible to B if and only if there is a polynomial-time computable function f such that, for all x, x∈ A if and only if f ∈ B. Two sets are: 1-equivalent if and only if each is m-reducible to the other by one-one reductions; p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and p-isomorphic if and only if there is an m-reduction from (...) one set to the other that is one-one, onto, and polynomial-time invertible. In this paper we show the following characterization. Theorem The following are equivalent: P = PSPACE. Every two 1-equivalent sets are p-isomorphic. Every two p-invertible equivalent sets are p-isomorphic. (shrink)

The degree structure of functions induced by a polynomial-time reducibility first introduced in G. Miller's work on the complexity of prime factorization is investigated. Several basic results are established including the facts that the degrees restricted to the sets do not form an upper semilattice and there is a minimal degree, as well as density for the low degrees, a weak form of the exact pair theorem, the existence of minimal pairs and the decidability of the (...) Π2 theory of the low degrees. (shrink)

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for (...) the structures of and will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

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)

We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.

The structure of the p-s-degrees of recursive functions is shown to be inhomogeneous. There are two p-s-degrees a and b above 0 such that [0, a] is distributive and [0, b] is nondistributive. Moreover, we will investigate how the number of values of each function reflects on its degree.

This research explores the relationship between the bounded in-degree and out-degree of an argumentation framework and the computational complexity of the problems of Credulous Acceptance ( CredA ) and Skeptical Acceptance ( SkepA ) under preferred extensions. Researchers have studied the complexity of these problems when the in-degree [Formula: see text] and out-degree [Formula: see text] of the arguments are restricted to [Formula: see text]. Despite this restriction, the computational complexities of CredA and SkepA persist. Based (...) on these results, we presents new results that provide deeper insights into the impact of additional constraints on the argumentation framework. Specifically, we show that when “[Formula: see text]” or “[Formula: see text]” is restricted to [Formula: see text], both problems CredA and SkepA can be solved in polynomial time. Subsequently, we impose additional constraints on the argumentation framework by analyzing the quantities “[Formula: see text],” “[Formula: see text],” and “[Formula: see text].” For an argumentation framework [Formula: see text] and all arguments “[Formula: see text]” of [Formula: see text], the parameter “[Formula: see text]” indicates the maximum number of attackers that any argument “[Formula: see text]” can have among all those that are not attacked by “[Formula: see text]” [Formula: see text], “[Formula: see text]” indicates the maximum number of arguments that any argument “[Formula: see text]” attacks among all those that do not attack “[Formula: see text]”, and “[Formula: see text]” denotes the maximum number of arguments that any argument “[Formula: see text]” attacks among those that attack “[Formula: see text]”. Surprisingly, even when all these quantities are restricted to [Formula: see text], the computational complexity of CredA persists. Furthermore, we explore the influence of symmetric attacks by fixing “[Formula: see text]” to zero, while setting “[Formula: see text]” and “[Formula: see text]” to [Formula: see text]. Remarkably, the complexity of CredA persists under this restriction as well. (shrink)

For a prime k, the embeddability of finite lattices are discussed for various kind of the MODkP degrees of recursive sets. In particular, all finite lattices are embeddable into the MODkP Turing degrees, whereas the non distributive lattice M3 is embeddable into the MOD2P many-one degrees but N5 is not.

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;.

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)

Deductive inference is usually regarded as being “tautological” or “analytical”: the information conveyed by the conclusion is contained in the information conveyed by the premises. This idea, however, clashes with the undecidability of first-order logic and with the (likely) intractability of Boolean logic. In this article, we address the problem both from the semantic and the proof-theoretical point of view. We propose a hierarchy of propositional logics that are all tractable (i.e. decidable in polynomial time), although by means (...) of growing computational resources, and converge towards classical propositional logic. The underlying claim is that this hierarchy can be used to represent increasing levels of “depth” or “informativeness” of Boolean reasoning. Special attention is paid to the most basic logic in this hierarchy, the pure “intelim logic”, which satisfies all the requirements of a natural deduction system (allowing both introduction and elimination rules for each logical operator) while admitting of a feasible (quadratic) decision procedure. We argue that this logic is “analytic” in a particularly strict sense, in that it rules out any use of “virtual information”, which is chiefly responsible for the combinatorial explosion of standard classical systems. As a result, analyticity and tractability are reconciled and growing degrees of computational complexity are associated with the depth at which the use of virtual information is allowed. (shrink)

Classical fractal dimensions have recently been effectivized by characterizing them in terms of real-valued functions called gales, and imposing computability and complexity constraints on these gales. This paper surveys these developments and their applications in algorithmic information theory and computational complexity theory.

Analogy and similarity are central phenomena in human cognition, involved in processes ranging from visual perception to conceptual change. To capture this centrality requires that a model of comparison must be able to integrate with other processes and handle the size and complexity of the representations required by the tasks being modeled. This paper describes extensions to Structure-Mapping Engine since its inception in 1986 that have increased its scope of operation. We first review the basic SME algorithm, describe psychological evidence (...) for SME as a process model, and summarize its role in simulating similarity-based retrieval and generalization. Then we describe five techniques now incorporated into the SME that have enabled it to tackle large-scale modeling tasks: Greedy merging rapidly constructs one or more best interpretations of a match in polynomial time: O); Incremental operation enables mappings to be extended as new information is retrieved or derived about the base or target, to model situations where information in a task is updated over time; Ubiquitous predicates model the varying degrees to which items may suggest alignment; Structural evaluation of analogical inferences models aspects of plausibility judgments; Match filters enable large-scale task models to communicate constraints to SME to influence the mapping process. We illustrate via examples from published studies how these enable it to capture a broader range of psychological phenomena than before. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* (...) such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial- (...) class='Hi'>time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous. (shrink)

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n (...) in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (shrink)

In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤r between subsets of the natural numbers, where ≤r is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown (...) by Ambos-Spies [2] in a setting of polynomial time bounds: given some recursively presentable ≤r-ideal I and some recursive ≤r-hard set B for I which is not contained in I, there is some recursive set C, where B and C are an exact pair for I, that is, I is equal to the intersection of the lower ≤r-cones of B and C, where C is not in I. In particular, if the relation ≤r is in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pair of recursive sets. (shrink)

A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable (...) equivalence relation is computably isomorphic to a p-time equivalence relation with standard universe. (shrink)

In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) (...) reduction is equivalent to the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65–76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes. (shrink)

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)

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.

Turing machines define polynomial time on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time ? Earlier, one of us conjectured a negative answer. The problem motivated a quest (...) for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines . The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime. (shrink)

This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the (...) orders are bounded, then the group is recursively isomorphic to a polynomial-time group with universe A being the set of tally representations of natural numbers Tal = s{;1s};* or the set of binary representations of the natural numbers Bin. We also construct a recursive Abelian group with all elements of finite order but which has elements of arbitrary large finite order which is not isomorphic to any polynomial-time group with universe Tal or Bin. Similar results are obtained for structures , where f is a permutation on the set A. (shrink)

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive (...) recursive structures, exponential-time structures and structures with honest witnesses. (shrink)

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.

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 prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = (...) 1, we show that the theory of the hpm-degrees is undecidable. We also show that index sets cannot be minimal. Lastly, we examine an alternative definition of honest m-reduction under which recursive minimal sets can be constructed. (shrink)

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 (...) class='Hi'>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)

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)

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)

Recently, Nerode and Remmel have developed a polynomial-time version of the theory of recursive equivalence types and have defined two analogues of isolatedness for that setting. This paper examines various properties of those two analogues and investigates their relationship to additive cancellability.

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 studies systems of explicit mathematics as introduced by Feferman [9, 11]. In particular, we propose weak explicit type systems with a restricted form of elementary comprehension whose provably terminating operations coincide with the functions on binary words that are computable in polynomial time. The systems considered are natural extensions of the first-order applicative theories introduced in Strahm [19, 20].

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...) }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel. (shrink)

Fragments of extensional Martin-Löf type theory without universes,ML 0, are introduced that conservatively extend S.A. Cook and A. Urquhart'sIPV ω. A model for these restricted theories is obtained by interpretation in Feferman's theory APP of operators, a natural model of which is the class of partial recursive functions. In conclusion, some examples in group theory are considered.

We propose two admissible closures $${\mathbb{A}({\sf PTCA})}$$ and $${\mathbb{A}({\sf PHCA})}$$ of Ferreira’s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) $${\mathbb{A}({\sf PTCA})}$$ is conservative over PTCA with respect to $${\forall\exists\Sigma^b_1}$$ sentences, and (ii) $${\mathbb{A}({\sf PHCA})}$$ is conservative over full bounded arithmetic PHCA for $${\forall\exists\Sigma^b_{\infty}}$$ sentences. This yields that (i) the $${\Sigma^b_1}$$ definable functions of $${\mathbb{A}({\sf PTCA})}$$ are the polytime functions, and (ii) (...) the $${\Sigma^b_{\infty}}$$ definable functions of $${\mathbb{A}({\sf PHCA})}$$ are the functions in the polynomial time hierarchy. (shrink)

A universal Horn sentence in the language of polynomial-time computable combinatorial functions of natural numbers is true for the natural numbers if, and only if, it is true for PETs of p-time p-isolated sets with functions induced by fully p-time combinatorial operators.

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorial grammar can be recognized in polynomial time.

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 (...) class='Hi'>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. (shrink)

The bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If T2i equals S2i + 1 then T2i is equal to S2 and proves that the polynomial time hierarchy collapses to ∑i + 3p, and, in fact, to the Boolean hierarchy over ∑i + 2p and to ∑i + 1p/poly.

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)

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)

In [7], a naive set theory is introduced based on a polynomial time logical system, Light Linear Logic (LLL). Although it is reasonably claimed that the set theory inherits the intrinsically polytime character from the underlying logic LLL, the discussion there is largely informal, and a formal justification of the claim is not provided sufficiently. Moreover, the syntax is quite complicated in that it is based on a non-traditional hybrid sequent calculus which is required for formulating LLL.In this (...) paper, we consider a naive set theory based on Intuitionistic Light Affine Logic (ILAL), a simplification of LLL introduced by [1], and call it Light Affine Set Theory (LAST). The simplicity of LAST allows us to rigorously verify its polytime character. In particular, we prove that a function over {0, 1}* is computable in polynomial time if and only if it is provably total in LAST. (shrink)

In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic definition of recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum (...) function from the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer. (shrink)