An arithmetical system is presented with the property that from every proof a realizing term can be extracted that is definable in a certain affine linear typed variant of Godel's T and therefore defines a non-siz...
详细信息
An arithmetical system is presented with the property that from every proof a realizing term can be extracted that is definable in a certain affine linear typed variant of Godel's T and therefore defines a non-size-increasing polynomial time computable function. (C) 2003 Elsevier B.V. All rights reserved.
We introduce a stratified version of Combinatory Logic(1) in which there are two classes of terms called player and opponent such that the class of player terms is strictly contained in the class of opponent terms. We...
详细信息
We introduce a stratified version of Combinatory Logic(1) in which there are two classes of terms called player and opponent such that the class of player terms is strictly contained in the class of opponent terms. We show that the system characterizes Polynomial Time in a similar way to Soft Linear Logic. With the addition of explicit "lazy" products to the player terms and various notions of distributivity, we obtain a characterization of Polynomial Space. This paper is an expanded version of the abstract presented at DICE 2013. (C) 2016 Elsevier Inc. All rights reserved.
We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as ...
详细信息
We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U-E*-uniform variant of NC1 Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence. (C) 2000 Elsevier Science B.V. All rights reserved.
In earlier work of Kristiansen and Niggl the polynomial-time computable functions were characterized by stack programs of mu-measure 0, and the linear-space computable functions by loop programs of mu-measure 0. Until...
详细信息
In earlier work of Kristiansen and Niggl the polynomial-time computable functions were characterized by stack programs of mu-measure 0, and the linear-space computable functions by loop programs of mu-measure 0. Until recently, an open problem was how to extend these characterizations to programs with user-friendly basic instructions, such as assignment statements, and with mixed data structures. It is shown how to strengthen the above characterizations to imperative programs built from arbitrary basic instructions by sequencing and by if-then-else and for-do statements. These programs operate on variables, each of which may represent any data structure such as stacks, registers, trees, or graphs. The paper presents a new method of certifying "polynomial size boundedness" of such imperative programs under the natural assumption that the basic instructions used are polynomially size bounded, too. The certificate for a program P with variables among X-1,...,X-n will be an (n+1) x (n+1) matrix M(P) over the finite set {0, 1,infinity}. It is shown that certified string programs (i.e., stack programs, but with any polynomial-time computable basic instructions) exactly compute the functions in FPTIME. Accordingly, certified general loop programs (using any linear-space computable basic instructions) exactly compute the functions in FLINSPACE. Furthermore, it is shown that certified power string programs (i.e., string programs, but built from polynomial-space computable basic instructions and extended by power loop statements) exactly compute the polynomial-space computable functions in FPSPACE. In addition, examples of certified "natural" (implementations of) algorithms, such as insertion-sort or binary addition and multiplication, are given.
Clarithmetics are number theories based on computability logic. Formulas of these theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic solutio...
详细信息
Clarithmetics are number theories based on computability logic. Formulas of these theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic solution. Various complexity constraints on such solutions induce various versions of clarithmetic. The present paper introduces a parameterized/schematic version CLA11(P4)(P1, P2, P3). By tuning the three parameters P-1, P-2, P-3 in an essentially mechanical manner, one automatically obtains sound and complete theories with respect to a wide range of target tricomplexity classes, i.e., combinations of time (set by P-3), space (set by P-2) and so called amplitude (set by P-1) complexities. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a solution from the given tricomplexity class and, furthermore, such a solution can be automatically extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a solution from the given tricomplexity class is represented by some theorem of the system. Furthermore, through tuning the 4th parameter P-4, at the cost of sacrificing recursive axiomatizability but not simplicity or elegance, the above extensional completeness can be strengthened to intensional completeness, according to which every formula representing a problem with a soli ion from the given tricomplexity class is a theorem of the system. This article is published in two parts. The previous Part I has introduced the system and proved its completeness, while the present Part II is devoted to proving soundness.
We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natural cost model in which lookup for an ...
详细信息
We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natural cost model in which lookup for an already computed result has no cost is indeed invariant. As a corollary, we then prove that the most general notion of ramified recurrence is sound for polynomial time, this way settling an open problem in implicit computational complexity. (C) 2018 The Authors. Published by Elsevier Inc.
When programming with sublinear space constraints one often needs to use special implementation techniques even for simple tasks, such as function composition. In this paper, we study how such implementation technique...
详细信息
When programming with sublinear space constraints one often needs to use special implementation techniques even for simple tasks, such as function composition. In this paper, we study how such implementation techniques can be supported in a functional programming language. Our approach is based on modelling computation by interaction using the Int construction of Joyal, Street & Verity. We apply this construction to a term model of a first-order programming language and use the resulting structure to derive the functional programming language INTML. INTML can be understood as a programming language simplification of Stratified Bounded Affine Logic. We formulate INTML by means of a type system inspired by Baillot & Terui's Dual Light Affine Logic. We show that it captures the complexity classes FLOGSPACE and NFLOGSPACE. We illustrate its expressiveness by showing how typical graph algorithms, such a test for acyclicity in undirected graphs, can be represented. (C) 2016 Elsevier Inc. All rights reserved.
We give a new characterization of elementary and deterministic polynomial time computation in linear logic through the proofs-as-programs correspondence. Girard's seminal results, concerning elementary and light l...
详细信息
We give a new characterization of elementary and deterministic polynomial time computation in linear logic through the proofs-as-programs correspondence. Girard's seminal results, concerning elementary and light linear logic, achieve this characterization by enforcing a stratification principle on proofs, using the notion of depth in proof nets. Here, we propose a more general form of stratification, based on inducing levels in proof nets by means of indices, which allows us to extend Girard's systems while keeping the same complexity properties. In particular, it turns out that Girard's systems can be recovered by forcing depth and level to coincide. A consequence of the higher flexibility of levels with respect to depth is the absence of boxes for handling the paragraph modality. We use this fact to propose a variant of our polytime system in which the paragraph modality is only allowed on atoms, and which may thus serve as a basis for developing lambda-calculus type assignment systems with more efficient typing algorithms than existing ones. (C) 2009 Elsevier B.V. All rights reserved.
New, simple, proofs of soundness (every representable function lies in a given complexity class) for Elementary Affine Logic, LFPL and Soft Affine Logic are presented. The proofs are obtained by instantiating a semant...
详细信息
New, simple, proofs of soundness (every representable function lies in a given complexity class) for Elementary Affine Logic, LFPL and Soft Affine Logic are presented. The proofs are obtained by instantiating a semantic framework previously introduced by the authors and based on an innovative modification of realizability. The proof is a notable simplification on the original already semantic proof of soundness for the above mentioned logical systems and programming languages. A new result made possible by the semantic framework is the addition of polymorphism and a modality to LFPL, thus allowing for an internal definition of inductive datatypes. The methodology presented proceeds by assigning both abstract resource bounds in the form of elements from a resource monoid and resource-bounded computations to proofs (respectively, programs). (C) 2010 Elsevier B.V. All rights reserved.
The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence...
详细信息
The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham's definition of FP by bounded recursion and for Bellantoni-Cook's safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and ne. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion. (C) 2003 Elsevier B.V. All rights reserved.
暂无评论