Polynomially Bounded Sequences and Polynomial Sequences

Hiroyuki Okazaki; Yuichi Futa

Formalized Mathematics (2015)

  • Volume: 23, Issue: 3, page 205-213
  • ISSN: 1426-2630

Abstract

top
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].

How to cite

top

Hiroyuki Okazaki, and Yuichi Futa. "Polynomially Bounded Sequences and Polynomial Sequences." Formalized Mathematics 23.3 (2015): 205-213. <http://eudml.org/doc/276434>.

@article{HiroyukiOkazaki2015,
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].},
author = {Hiroyuki Okazaki, Yuichi Futa},
journal = {Formalized Mathematics},
keywords = {computational complexity; polynomial time},
language = {eng},
number = {3},
pages = {205-213},
title = {Polynomially Bounded Sequences and Polynomial Sequences},
url = {http://eudml.org/doc/276434},
volume = {23},
year = {2015},
}

TY - JOUR
AU - Hiroyuki Okazaki
AU - Yuichi Futa
TI - Polynomially Bounded Sequences and Polynomial Sequences
JO - Formalized Mathematics
PY - 2015
VL - 23
IS - 3
SP - 205
EP - 213
AB - 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].
LA - eng
KW - computational complexity; polynomial time
UR - http://eudml.org/doc/276434
ER -

References

top
  1. [1] Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990. Zbl06213858
  2. [2] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  3. [3] Grzegorz Bancerek. Increasing and continuous ordinal sequences. Formalized Mathematics, 1(4):711-714, 1990. 
  4. [4] Grzegorz Bancerek and Piotr Rudnicki. Two programs for SCM. Part I - preliminaries. Formalized Mathematics, 4(1):69-72, 1993. 
  5. [5] E.J. Barbeau. Polynomials. Springer, 2003. 
  6. [6] Czesław Bylinski. The complex numbers. Formalized Mathematics, 1(3):507-513, 1990. 
  7. [7] Czesław Bylinski. Functions and their basic properties. Formalized Mathematics, 1(1): 55-65, 1990. 
  8. [8] Czesław Bylinski. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  9. [9] Czesław Bylinski. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  10. [10] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990. 
  11. [11] Jon Kleinberg and Eva Tardos. Algorithm Design. Addison-Wesley, 2005. 
  12. [12] Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. Zbl0895.68055
  13. [13] Artur Korniłowicz. On the real valued functions. Formalized Mathematics, 13(1):181-187, 2005. 
  14. [14] Jarosław Kotowicz. The limit of a real function at infinity. Formalized Mathematics, 2 (1):17-28, 1991. 
  15. [15] Jarosław Kotowicz. Real sequences and basic operations on them. Formalized Mathematics, 1(2):269-272, 1990. 
  16. [16] Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part I: Theory. Formalized Mathematics, 9(1):135-142, 2001. 
  17. [17] Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part II: Examples and problems. Formalized Mathematics, 9(1):143-154, 2001. 
  18. [18] Yatsuka Nakamura and Hisashi Ito. Basic properties and concept of selected subsequence of zero based finite sequences. Formalized Mathematics, 16(3):283-288, 2008. doi:10.2478/v10037-008-0034-y.[Crossref] 
  19. [19] Jan Popiołek. Some properties of functions modul and signum. Formalized Mathematics, 1(2):263-264, 1990. 
  20. [20] Konrad Raczkowski and Andrzej Nedzusiak. Real exponents and logarithms. Formalized Mathematics, 2(2):213-216, 1991. 
  21. [21] Konrad Raczkowski and Andrzej Nedzusiak. Series. Formalized Mathematics, 2(4):449-452, 1991. 
  22. [22] Konrad Raczkowski and Paweł Sadowski. Real function differentiability. Formalized Mathematics, 1(4):797-801, 1990. 
  23. [23] Yasunari Shidama. The Taylor expansions. Formalized Mathematics, 12(2):195-200, 2004. 
  24. [24] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990. 
  25. [25] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  26. [26] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825-829, 2001. 
  27. [27] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1 (1):73-83, 1990. 
  28. [28] Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.