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

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

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