Log in

Relevant bibliographies by topics / Arithmetic Complexity Classes

Contents

Journal articles
Book chapters
Conference papers

Academic literature on the topic 'Arithmetic Complexity Classes'

Author: Grafiati

Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Arithmetic Complexity Classes.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Arithmetic Complexity Classes"

1

G�l, Anna, and Avi Wigderson. "Boolean complexity classes vs. their arithmetic analogs." Random Structures and Algorithms 9, no. 1-2 (1996): 99–111. http://dx.doi.org/10.1002/(sici)1098-2418(199608/09)9:1/2<99::aid-rsa7>3.0.co;2-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Ignjatović, Aleksandar. "Delineating classes of computational complexity via second order theories with weak set existence principles. I." Journal of Symbolic Logic 60, no. 1 (1995): 103–21. http://dx.doi.org/10.2307/2275511.

Full text

Abstract:

AbstractIn this paper we characterize the well-known computational complexity classes of the polynomial time hierarchy as classes of provably recursive functions (with graphs of suitable bounded complexity) of some second order theories with weak comprehension axiom schemas but without any induction schemas (Theorem 6). We also find a natural relationship between our theories and the theories of bounded arithmetic (Lemmas 4 and 5). Our proofs use a technique which enables us to “speed up” induction without increasing the bounded complexity of the induction formulas. This technique is also used

APA, Harvard, Vancouver, ISO, and other styles

3

Jeřábek, Emil. "Approximate counting in bounded arithmetic." Journal of Symbolic Logic 72, no. 3 (2007): 959–93. http://dx.doi.org/10.2178/jsl/1191333850.

Full text

Abstract:

AbstractWe develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV1 + dWPHP(PV).

APA, Harvard, Vancouver, ISO, and other styles

4

Japaridze, Giorgi. "Arithmetics based on computability logic." Logical Investigations 25, no. 2 (2019): 61–74. http://dx.doi.org/10.21146/2074-1472-2019-25-2-61-74.

Full text

Abstract:

This paper is a brief survey of number theories based on em computability logic (CoL) a game-semantically conceived logic of computational tasks of resources. Such theories, termed em clarithmetics, are conservative extensions of first-order Peano arithmetic.   The first section of the paper lays out the conceptual basis of CoL and describes the relevant fragment of its formal language, with so called parallel connectives, choice connectives and quantifiers, and blind quantifiers. Both syntactically and semantically, this is a conservative generalization of the language of classica

APA, Harvard, Vancouver, ISO, and other styles

5

Kupke, Clemens, Dirk Pattinson, and Lutz Schröder. "Coalgebraic Reasoning with Global Assumptions in Arithmetic Modal Logics." ACM Transactions on Computational Logic 23, no. 2 (2022): 1–34. http://dx.doi.org/10.1145/3501300.

Full text

Abstract:

We establish a generic upper bound ExpTime for reasoning with global assumptions (also known as TBoxes) in coalgebraic modal logics. Unlike earlier results of this kind, our bound does not require a tractable set of tableau rules for the instance logics, so that the result applies to wider classes of logics. Examples are Presburger modal logic, which extends graded modal logic with linear inequalities over numbers of successors, and probabilistic modal logic with polynomial inequalities over probabilities. We establish the theoretical upper bound using a type elimination algorithm. We also pro

APA, Harvard, Vancouver, ISO, and other styles

6

Harnik, Victor. "Provably total functions of intuitionistic bounded arithmetic." Journal of Symbolic Logic 57, no. 2 (1992): 466–77. http://dx.doi.org/10.2307/2275282.

Full text

Abstract:

This note deals with a proof-theoretic characterisation of certain complexity classes of functions in fragments of intuitionistic bounded arithmetic. In this Introduction we survey the background and state our main result.We follow Buss [B1] and consider a language for arithmetic whose nonlogical symbols are 0, S (the successor operation Sx = x + 1), +, ·, ∣ ∣ (∣x∣ being the number of digits in the binary notation for x), rounded down to the nearest integer), # (x#y = 2∣x∣∣y∣) and ≤. We define 1 = S0, 2 = S1, s0x = 2x and s1x = 2x + 1. In Buss's approach the functions s0 and s1 play a special

APA, Harvard, Vancouver, ISO, and other styles

7

Zeschke, Yorick. "Growth Functions, Rates and Classes of String-Based Multiway Systems." Complex Systems 31, no. 1 (2022): 123–64. http://dx.doi.org/10.25088/complexsystems.31.1.123.

Full text

Abstract:

Inspired by the recently emerging Wolfram Physics Project where “Multiway Systems,” graph representations of abstract rewriting systems equipped with a causal structure, have played an important role in discrete models of spacetime and quantum mechanics, this paper establishes several more fundamental properties about the growth (number of states over steps in a system’s evolution) of string rewriting systems in general. While proving the undecidability of exactly determining a system’s growth function, we show several asymptotic properties all growth functions of arbitrary string rewriting sy

APA, Harvard, Vancouver, ISO, and other styles

8

Leivant, Daniel, and Bob Constable. "Editorial." Journal of Functional Programming 11, no. 1 (2001): 1. http://dx.doi.org/10.1017/s0956796801009030.

Full text

Abstract:

This issue of the Journal of Functional Programming is dedicated to work presented at the Workshop on Implicit Computational Complexity in Programming Languages, affiliated with the 1998 meeting of the International Conference on Functional Programming in Baltimore.Several machine-independent approaches to computational complexity have been developed in recent years; they establish a correspondence linking computational complexity to conceptual and structural measures of complexity of declarative programs and of formulas, proofs and models of formal theories. Examples include descriptive compl

APA, Harvard, Vancouver, ISO, and other styles

9

Guzhov, Vladimir I., Ilya O. Marchenko, Ekaterina E. Trubilina, and Dmitry S. Khaidukov. "Comparison of numbers and analysis of overflow in modular arithmetic." Analysis and data processing systems, no. 3 (September 30, 2021): 75–86. http://dx.doi.org/10.17212/2782-2001-2021-3-75-86.

Full text

Abstract:

The method of modular arithmetic consists in operating not with a number, but with its remainders after division by some integers. In the modular number system or the number system in the residual classes, a multi-bit integer in the positional number system is represented as a sequence of several positional numbers. These numbers are the remainders (residues) of dividing the original number into some modules that are mutually prime integers. The advantage of the modular representation is that it is very simple to perform addition, subtraction and multiplication operations. In parallel executio

APA, Harvard, Vancouver, ISO, and other styles

10

Zadiraka, Valerii, and Inna Shvidchenko. "Using Rounding Errors in Modern Computer Technologies." Cybernetics and Computer Technologies, no. 3 (September 30, 2021): 43–52. http://dx.doi.org/10.34229/2707-451x.21.3.4.

Full text

Abstract:

Introduction. When solving problems of transcomputational complexity, the problem of evaluating the rounding error is relevant, since it can be dominant in evaluating the accuracy of solving the problem. The ways to reduce it are important, as are the reserves for optimizing the algorithms for solving the problem in terms of accuracy. In this case, you need to take into account the rounding-off rules and calculation modes. The article shows how the estimates of the rounding error can be used in modern computer technologies for solving problems of computational, applied mathematics, as well as

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Arithmetic Complexity Classes"

1

Chen, Hubie. "Arithmetic Constant-Depth Circuit Complexity Classes." In Mathematical Foundations of Computer Science 2003. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-45138-9_27.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Clote, Peter, and Gaisi Takeuti. "First Order Bounded Arithmetic and Small Boolean Circuit Complexity Classes." In Feasible Mathematics II. Birkhäuser Boston, 1995. http://dx.doi.org/10.1007/978-1-4612-2566-9_6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Hofmann, Martin. "From Bounded Arithmetic to Memory Management: Use of Type Theory to Capture Complexity Classes and Space Behaviour." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45413-6_2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Arithmetic Complexity Classes"

1

Hasan, M. A., and C. Negre. "Subquadratic Space Complexity Multiplier for a Class of Binary Fields Using Toeplitz Matrix Approach." In 2009 IEEE 19th IEEE Symposium on Computer Arithmetic (ARITH). IEEE, 2009. http://dx.doi.org/10.1109/arith.2009.15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!