s2009_33 писал(а):Source of the post Как бы это сказать..Интересуют не лекции (хотя и они тоже). А грамотное объяснение сути теоремы, размером несколько строк. Но на общедоступном языке.
вас не интересуют, а других могут заинтересовать
сути какой теоремы? которую никто не доказал? пока говорить не о чем
суть
проблемы следующая
1. Все задачи классифицируются по вычислительной сложности наилучшего (самого быстрого) алгоритма, известного для ея решения.
Вычислительная сложность алгоритма меряется по "самому плохому случаю" и выражается как функция от размерности исходных данных. Такая сложность называется асимптотической и показывает, как быстро растёт время работы алгоритма при увеличении размерности входных данных.
Например, если сортируем массив алгоритмом "пузырёк", то число шагов этого алгоритма растёт пропорционально квадрату числа элементов массива.
2. Все задачи из класса P, которые решаются "эффективными" алгоритмами (эффективный = полиномиальный) давно решены. Эти алгоритмы нетрудно выучить, и ещё надо уметь делать постановки реальных задач так, чтобы можно было воспользоваться эффективными алгоритмами, это требует определённой квалификации и этому нигде не учат.
3. Есть так называемые NP-полные задачи, которые возникают на каждом шагу на производстве и в науке, конечно... на самом деле, чего не коснись - везде NP-полные задачи...
так вот, все точные алгоритмы, известные для решения NP-полных задач, экспоненциальные, то есть их можно решать точно только для малой размерности. Справедливости ради замечу, что псевдополиномиальными алгоритмами можно решать среднюю размерность.
Но в реальных NP-полных задачах обычно большая и сверхбольшая размерность, поэтому их приходится решать приближёнными (известна скорость сходимости к точному решению или известна оценка погрешности) или эвристическими алгоритмами (ничего не известно).
Поэтому надо
или доказать, что NP-полные задачи нельзя рещить за полиномиальное время и на этом успокоиться,
или для какой-то NP-полной задачи найти полиномиальный алгоритм. Поскольку NP-полные задачи между собой эквивалентны, в смысле полиномиальной сводимости, то все они будут решены за полиномиальное время и P=NP.