<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].</p></abstract>

In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].

Polynomially Bounded Sequences and Polynomial Sequences

Japan Advanced Institute of Science and Technology Ishikawa, Japan

Formalized Mathematics

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License.

{"article-title":"Polynomially Bounded Sequences and Polynomial Sequences"}

In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental...

Polynomially Bounded Sequences and Polynomial Sequences

Publié en ligne: 30 sept. 2015

Pages: 205 - 213

Reçu: 30 juin 2015

DOI: https://doi.org/10.1515/forma-2015-0017

Mots clés
computational complexity, polynomial time

© by Hiroyuki Okazaki

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License.

Polynomially Bounded Sequences and Polynomial Sequences

Publié en ligne: 30 sept. 2015

Pages: 205 - 213

Reçu: 30 juin 2015

DOI: https://doi.org/10.1515/forma-2015-0017

Mots cléscomputational complexity, polynomial time

© by Hiroyuki Okazaki

This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 License.

Mots clés
computational complexity, polynomial time