Обсуждение:Теорема Бермана — Форчуна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(ToDo)
(нет различий)

Версия 02:01, 18 апреля 2012

ToDo

  • Прям вот так сразу: надо было придумать другое название статьи, потому что это нас не устаивает.
  • Нет сслылок на определения [math]NPC[/math] и [math]coNPC[/math].
  • Ты пользуешься фактом, что [math](L_1 \leq L_2) \Leftrightarrow (\overline{L_1} \leq \overline{L_2})[/math]. Этот факт неочевиден, ссылку в студию! (это в моём конспекте должно быть).
  • В определении [math]TAUT[/math] стоит написать, что эта [math]\phi[/math] — это булева формула, потому что навскидку это не понять.
  • Косметическая правка: «тогда по лемме 1 [math]TAUT[/math]…» единица с [math]TAUT[/math] сливаются, попробуй написать «по лемме (1)…».
  • Псевдокод [math]check(\phi, i)[/math], очевидно, неверен. Хотя бы потому что случаи [math] \phi = 0 [/math] и [math] \phi = 1 [/math] недостижимы. Во втором псевдокоде та же бага, исправь, после я буду читать дальше.