Класс co-NP — различия между версиями

Версия 18:33, 18 марта 2010

В теории сложности Класс [math]coNP[/math] — класс языков (задач), дополнение к которым является NP.

Если [math]NP \ne coNP[/math], тогда [math]P \neq NP[/math]

Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT

Версия 16:57, 18 марта 2010 (просмотреть исходный код) Andrew Stankevich (обсуждение \| вклад) ← Предыдущая правка		Версия 18:33, 18 марта 2010 (просмотреть исходный код) Perovskaya (обсуждение \| вклад) Следующая правка →
Строка 1:		Строка 1:
−	В теории сложности '''Класс ~~coNP~~''' - класс языков (задач), дополнение к которым является NP.	+	В теории сложности '''Класс''' <tex>coNP</tex> — класс языков (задач), дополнение к которым является NP.

	==Теоремы, связанные с coNP==		==Теоремы, связанные с coNP==