Обсуждение:Теория алгоритмов
Перейти к навигации
Перейти к поиску
 | Статья «Теория алгоритмов» входит в общий для всех языковых разделов Википедии расширенный список необходимых статей. Её развитие вплоть до статуса избранной является важным направлением работы русского раздела Википедии. |
Проект «Информационные технологии» (уровень I, важность для проекта высшая)
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Обсуждение[править код]
«…проводит классификацию задач по классам сложности P и NP.» Или я чего-то не понимаю, или автор слишком вольно толкует понятие NP-задачи, но мне всегда казалось, что существуют задачи не входящие ни в класс P, ни в класс NP (например, разрешимые только за экспоненциальное время). Я не прав?--Begemotv2718 19:17, 11 августа 2005 (UTC)
- Прав, конечно. Дописывай :) ==Maxim Razin(talk) 19:47, 11 августа 2005 (UTC)
- Нет, не правы. В класс NP входят все неполиномиальные алгоритмы, в т.ч. и алгоритмы с экспоненциальным и факториальным временем. см. напр. Дж. Макконел, Анализ алгоритмов. Удалил ссылку на "другие классы сложности" "до выяснения обстоятельств": кто и где так классифицирует. leseul
- У нас свои авторитеты А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления.--Begemotv2718 01:18, 12 августа 2005 (UTC)
- Вынужден вас разочаровать. NP это класс недетерминистически полиномиальных алгоритмов, т.е. алгоритмов, решение которых можно проверить за полиномиальное время. Поэтому есть и алгоритмы не входящие в NP (все алгоритмы из P входят в NP, кстати). Ornil 23:50, 11 августа 2005 (UTC)
- Кстати, я правильно понимаю, что задача о факторизации числа на простые множители входит в класс NP (простоту числа можно проверить за полиномиальное время, как недавно доказали), но её NP-полнота не доказана?--Begemotv2718 01:11, 12 августа 2005 (UTC)
- По–моему верно. Ornil 01:14, 12 августа 2005 (UTC)
- Кстати, я правильно понимаю, что задача о факторизации числа на простые множители входит в класс NP (простоту числа можно проверить за полиномиальное время, как недавно доказали), но её NP-полнота не доказана?--Begemotv2718 01:11, 12 августа 2005 (UTC)
- А я и не разочаровался :-). Дописывайте! Только проблему P=NP не потеряйте :) И еще, не надо слишком раздувать этот раздел, чтобы текст не вышел слишком длинным. Надо ведь ещё написать про асимптотический анализ и практическую теорию. --LeSeul 01:44, 12 августа 2005 (UTC)