Основы доказательств полиномиальной быстроты простейших математических алгоритмов

  • Т.М. Косовская
  • Н.К. Косовский
  • Татьяна Косовская
Keywords: P, FP, NP, машина тьюринга, паслкалевидные функции, NP-полнота, NP-трудность, примеры NP-полных задач

Abstract

Статья посвящена проблемам доказательства полиномиальной вычислимости функций, другими словами, доказательства принадлежности функций классу FP. Доказательства могут производиться с помощью паскалевидных функций, которые более удобны программистам, чем модели вычислений, основанные на машине Тьюринга. Будет приведена идея доказательства теоремы, что если не только число шагов вычисления паскалевидной функции, но и размер записи всех промежуточных вычислений не превосходят полинома от длины записи исходных данных, то эта функция принадлежит классу FP и обратно.

References

1.
2.
Published
2014-01-22
How to Cite
Косовская, Т., Косовский, Н., & Косовская, Т. (2014). Основы доказательств полиномиальной быстроты простейших математических алгоритмов. Computer Tools in Education, (2). Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1211
Issue
No 2 (2010)
Section
Informatics and Algorithmic Mathematics

Most read articles by the same author(s)