Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Язык планарных графов — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/язык планарных графов в [[Полиномиальные своди…)
 
(не показано 15 промежуточных версий этого же участника)
Строка 1: Строка 1:
[[Category:Предложенные студентами задачи|Предложенные студентами задачи]]
 
 
<latex>
 
<latex>
 
Пусть L_{planar} - \text{это язык планарных графов (как обычно, считаем, что графы задаются списком ребер или матрицей смежности)}.  
 
Пусть L_{planar} - \text{это язык планарных графов (как обычно, считаем, что графы задаются списком ребер или матрицей смежности)}.  
Строка 6: Строка 5:
  
 
Подсказка: посмотри Th. Понтрягина — Куратовского
 
Подсказка: посмотри Th. Понтрягина — Куратовского
 +
</latex>
 +
 +
[[Категория:Решенные задачи]]

Текущая версия на 17:13, 11 октября 2020