1) Если µ, то Î Р Þ Î Р;
2) Если µи µ, то µ;
3) Если Î NР, Î NР, Î NРС и µ, то Î NРС. Доказательство вытекает из определений 2.1, 3.1, 4.1 и 4.2.
Теорема 4.1 указывает способ доказательства. NР -полноты некоторой задачи Z, если известна хотя он одна NР -полная задача Z*: достаточно доказать, что Î NР и что Z*µ Z.
Если предположить, что классы P и NP совпадают, что означает существование полиномиального алгоритма решения любой задачи из NP, то это повлекло бы существование полиномиальных алгоритмов решения всех NР -полных задач. Однако за всю историю развития математики не было найдено ни одного полиномиального алгоритма решения хотя бы одной какой-нибудь известной NР -полной задачи. Это послужило обоснованием существующей на сегодняшний день научной гипотезы
P ≠ NP
На рис.4.2 приведена теоретико-множественная диаграмма класса NP в предположении, что P ¹ NP.
Литература:
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. – 416 с.
2. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. – 536 с.
3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.
4. Донской В. И. Дискретная математика. –Симферополь: Сонат, 2000. –356 с.
5. Липский В. Комбинаторика для программистов. М.: Мир, 1988. – 215 с.
6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995. – 256 с
7. Линдон Р. Заметки по логике. М.: Мир, 1968. – 128 с.
8. Оре О. Теория графов. М.: Наука, 1980. – 336 с.
9. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. – 400 с.