7 Неразрешимых проблем:
Проблема распознавания истинности формул в элемент.арифметике – проблема требования найти алгоритм. который по всякой формуле определял бы истина она в натур. ряду или нет. Невозможность такого алгоритма следует из перечисл. множества натуральных чисел.
Проблема разрешения для логики предикатов I-ого порядка (1936г.) – вытекает из особенности предиката (вход данные бесконечны, а вых. только 0 и 1)
Проблема разрешимости Поста – Пусть дано конечное множество пар в некотор. алфавите (сочетаемом) .Если для рассмат. пар
…
выполняется
,
…
=
,
…
.
Проблема разрешима если алфавит
однобуквенный.Проблема эквивалентности слов для ассоциативного исчисления – сформулировал Туэ: «Пусть дано 2 кортежа A и B. Найти алгоритм позволяющий из исчислимого числа операций всегда решать будит ли эвивал. 2 произвольных ряда знаков)»
Требуется построить алгоритм распознающий по вской паре В-слов эквивалентны ли слова в данном вычислении или нет.
Проблема представимости матриц. – матр. И представима через матр.
если
для некотор. индексов выполняется
равенство
Общая
проблема представимости состоит в
требовании указать алгоритм по средствам
которого можно было бы узнавать для
любой системы матриц {
}
представима ли И через
…
Марков
доказал что проблема неразрешима для
матриц размерности
10-я проблема Гильберта -Задачи разрешимости диофантовогоур-ия
Проблема тождества элементарных функций вещественных переменных. Проблема указать алгоритм узнающий по 2-ум термам задают ли они одну и тужу функцию веществен.переменного
Вопрос 49
В теории алгоритмовNP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если длякакой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Формальное определение
Алфавитом
называется всякое конечное множествосимволов
(например,
или
).
Множество всех возможныхслов
(конечных строк,
составленных из символов этого алфавита)
над некоторым алфавитом
обозначается
.Языком
над
алфавитом
называется
всякоеподмножество
множества
,
то есть
.
Задачей
распознавания
для языка
называется
определение того, принадлежит ли данное
слово языку
.
Язык
называетсясводимым
(по Карпу)
к языку
,
если существуетфункция,
,
вычислимая заполиномиальное
время,
обладающая следующим свойством:
тогда
и только тогда, когда
Сводимость
по Карпу обозначается как
или
.
Язык
называетсяNP-трудным,
если любой язык из класса NP сводится к
нему. Язык называют NP-полным,
если он NP-труден, и при этом сам лежит в
классе NP.
Таким образом, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в классе P, то есть будут решаться за полиномиальное время.
NP-полнота в сильном смысле
Задача называется NP-полной в сильном смысле, если у неё существует подзадача, которая:
не является задачей с числовыми параметрами (т.е. максимальное значение величин, встречающихся в этой задаче ограничено сверху полиномом от длины входа),
принадлежит классу NP,
является NP-полной.
Класс таких задач называется NPCS. Если гипотеза P ≠ NP верна, то для NPCS задачи не существует псевдополиномиального алгоритма.
Примеры NP-полных задач
Задача о выполнимости булевых формул
Кратчайшее
решение «пятнашек» размера 
Задача коммивояжёра
Проблема Штейнера
Проблема раскраски графа
Задача о вершинном покрытии
Задача о покрытии множества
Задача о клике
Задача о независимом множестве
Сапер (игра)
Тетрис[2]