Понятие о вычислимых, всюду определенных, частичных и частично- рекурсивных функциях. Тезис Черча

Числовые функции, значения которых можно вычислить посредством применения некоторого алгоритма, называются эффективно вычислимыми (или просто вычислимыми) функциями.

Функция называется всюду определенной, если область ее определения, т.е. множество значений ее аргумента и область значений функций, каждому из которых сопоставлено некотороезначение аргумента, совпадают.

Функции, определенные не для всех значений аргументов, называются частичными (не всюду определенными) функциями.

Частично-рекурсивные функции – это функции, определяемые особым образом с достаточной математической строгостью. А именно: если функция может быть получена за конечное число шагов из некоторых простейших функций с помощью операций суперпозиции, примитивной рекурсии и операции минимизации.

С.К. Клини (американский логик и математик) высказал гипотезу о том, что класс алгоритмически вычислимых частичных функций совпадает с классом всех частично рекурсивных функций. Ранее аналогичную гипотезу относительно всюду определенных вычислимых функций выдвинул А Чёрч (американский логик и математик). Гипотезы Чёрча и Клини обычно объединяют в виде тезиса Чёрча.

19. Понятие о труднорешаемых, NP, P и NP-полных задачах. Взаимоотношение классов P, NP и NP-полных задач.

Широкое распространение получило соглашение о том, что задача не считается эффективно решаемой до тех пор, пока для нее не будет получен полиномиальный алгоритм. В связи с этим вводят термин труднорешаемой задачи, если для нее не существует полиномиального алгоритма.

Аббревиатура NP происходит от английских слов nondeterministic (N) и polinomial (P) и означает класс всех задач распознавания, которые могут быть решены НДВУ за полиномиальное время. В отличие от этих задач класс задач, полиномиально разрешимых на детерминированной одноленточной машине Тьюринга (ДМТ), стали называть классом P (от слова polinomial).

После того как было введено понятие класса задач NP,было доказано, что многие хорошо известные комбинаторные задачи, будучи сформулированы как задачи распознавания, оказываются эквивалентными по трудности задаче о выполнимости. Этот класс эквивалентности, состоящий из “самых трудных” задач, принадлежащих к классу NP, получил название класса NP - полных задач. Иногда его называют классом универсальных задач, которые упрощенно понимают как задачи, для которых не найдены полиномиальные алгоритмы. Однако и не доказано, что таких алгоритмов вообще не существует.