Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Проблемы решения разбиваются на классы сложности, каждый из которых имеет свои ограничения на время и пространство решения проблемы.

В теории вычислимости выделяют большое число классов сложности (P,NP,NP-тяжелая, Co-NP и т.д.). Ниже приводятся определения лишь нескольких классов сложности.

Класс сложности P - проблема может быть решена за полиномиальное время на обычном компьютере.

NP класс (NP - недетерминистское полиномиальное время):

· Проблема решения принадлежит к NP классу сложности, если она может быть решена в полиномиальное время на недетерминистском компьютере. Недетерминистский компьютер содержит экспоненциально много параллельно работающих обычных компьютеров, каждый из которых может дать ответ «да» в полиномиальное время без консультации с другими компьютерами.

· Класс проблем, которые «чуть сложнее» чем Р класс.

· В общем случае экспоненциальное число под проблем, каждая из которых решается или доказывается в полиномиальное время.

· Нахождение в NP классе дает нижнюю границу сложности проблемы.

NP-тяжелой класс:

· Проблема Q является NP-тяжелой, если каждая проблема в NP сводится к проблеме Q.

· Нижняя граница сложности: «по крайней мере такая же тяжелая, как любая проблема в NP-классе»

NP-полный класс:

· Самые тяжелые проблемы в NP-классе.

· Если найден алгоритм полиномиального времени для NP-полной проблемы, тогда имеется алгоритм полиномиального времени для каждой проблемы в NP-классе.

· Устанавливает нижнюю и верхнюю границы сложности решения.

Широко распространено мнение, что NP и NP-тяжелые проблемы решаются за время, большее, чем полиномиальное время, однако строго это не было доказано.

Традиционная «атака» на NP-тяжелые проблемы состоит в следующем:

· придумываются алгоритмы для нахождения точных решений (они будут работать быстро только для относительно малых размеров проблемы);

· придумываются «субоптимальные» или эвристические алгоритмы, т.е. алгоритмы, дающие, возможно, хорошие решения, но доказать их оптимальность невозможно;

· нахождение специальных случаев проблемы («субпроблемы»), для которых возможны либо точные, либо лучшие эвристические алгоритмы.