Классы сложности

13.08.2010

Сотрудник лаборатории Hewlett-Packard в Пало-Альто индиец Винэй Деолаликар (Vinay Deolalikar) написал статью, в которой сделал вывод, что классы сложности P и NP не равны.

Задачи класса сложности P можно решить за адекватное время.

Пример задачи класса сложности NP – это сборка мозаики вслепую. Вы легко можете определить, правильно ли уложены все кусочки, но вот получить, скажем, Мону Лизу из тысячи разноцветных кусочков, перебирая различные их сочетания, уже не так просто.

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

Эта задача тысячелетия чрезвычайно важна для специалистов, занимающихся теориями компьютерных вычислений и шифрования данных.

Комментарий

Следствие: за большинством историй успеха стоит инсайдер , подсказывающий, как "вслепую" складывать "мозаику". Очевидно, что жульничество, но, как говорится: не пойман - не вор, а авторитет.

Постоянный адрес статьи в Интернет: http://www.ispl.ru/Klassy_slozhnosti.html

Ключевые слова: задача тысячелетия, классы сложности, инсайдер, вор, авторитет, мозаика, Мона Лиза

Наука
Главная
(C) Л.Точилов