<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

Publicado en línea: 30 sept 2015

Páginas: 205 - 213

Recibido: 30 jun 2015

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

Palabras clave
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

Publicado en línea: 30 sept 2015

Páginas: 205 - 213

Recibido: 30 jun 2015

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

Palabras clavecomputational complexity, polynomial time

© by Hiroyuki Okazaki

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

Palabras clave
computational complexity, polynomial time