Теория вычислимости
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
открытых проблем в области теоретической информатики. Математический институт Клэя за её решение.
Каждый класс сложности (в узком смысле) определяется как множество предикатов, обладающих некоторыми свойствами. Типичное определение класса сложности выглядит так:
">Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга (f(n)) ресурса, где n - длина слова x.
В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы). Языки, распознаваемые предикатами из некоторого класса (то есть множества слов, на которых предикат возвращает 1), также называются принадлежащими тому же классу.
">Кроме того, многие классы могут также быть описаны в терминах математической логики .
Классы принято обозначать прописными буквами. Дополнение к классу C (то есть класс языков, дополнения которых принадлежат C) обозначается co-C.
Отношения между классами
Все классы сложности находятся в иерархическом отношении: одни включают в себя другие. Однако про большинство включений неизвестно, являются ли они строгими. Одна из наиболее известных открытых проблем в этой области - .(),..
(1936),,,.
Заключение
класс сложность алгоритм
">В настоящее время исследования по теории вычислимости активно ведутся во всех странах мира. Россия всегда была одним из мировых центров исследований по теории вычислимости и её приложениям. Эти исследования берут начало от ранних работ Маркова ">в Н