V
Задачи, решение которых можно найти за полиномиальное время лежат в классе азадач P
Size: a a a
2017 September 04
V
Есть еще класс задач NP, это такие задачи, для которых, если известно решение, то можно проверить его корректность за полиномиальное время
V
P вложено в NP
N
опять же, в @nerdlair набрасывал на эту тему, включая ссылки :)
ПП
Есть еще класс задач NP, это такие задачи, для которых, если известно решение, то можно проверить его корректность за полиномиальное время
Но вот найти решения, наверное, нельзя
ПП
V
для некоторых классов, есть такие универсальные задачи, к которым сводимы все остальные задачи из этого класса
например, есть NP-трудные задачи, типа SAT, CSAT, поиск Гамильтонова цикла в графе, к ним за полиномиальное время сводятся все другие задачи из класса NP
например, есть NP-трудные задачи, типа SAT, CSAT, поиск Гамильтонова цикла в графе, к ним за полиномиальное время сводятся все другие задачи из класса NP
V
Но вот найти решения, наверное, нельзя
не известно, потому что не известно P!=NP
V
если P != NP, то существует непустой класс NPI, это задачи из NP, но не NP-трудные
V
к таким задачам потенциально относят, например, вершиноое покрытие или ТА-ДА дискретный логарифм
V
если P != NP, то квантовый компьютер может быть эффективнее хотя бы на NPI задачах
V
также есть класс PSPACE, время для таких задач не ограничено, но память должна быть полиномиальная
очевидно, что NP, а следовательно и P вложены в PSPACE
очевидно, что NP, а следовательно и P вложены в PSPACE
L
есть в хайрезе? алсо не учтена роль константы 😏
V
в PSPACE также вложен BQP, класс задач, которые эффективно решаются на квантовом компьютере
V
если удастся доказать, что BQP и P друг в друга не входят целиком, то P != PSPACE -- это кстати задача не менее интересная, чем P vs NP
V
класс BQP -- это основной класс задач, на который нацелен квантовый компьютер
V
он аналогичен классу BPP -- класс задач, которые решаются за полиномиальное время на классическом компьютере, с точностью не менее 3/4, то есть в 1/4 части случаев алгоритм может выдавать ошибку
V
показано, однако, что с ростом количества повторений прогонов таких алгоритмов вероятность ошибки убывает экспоненциально
V
поэтому этот класс очень практичен