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

Материал из Викиконспекты
Перейти к: навигация, поиск
(ToDo)
 
(Омг: Новая тема)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 5: Строка 5:
 
* В определении <tex>TAUT</tex> стоит написать, что эта <tex>\phi</tex> — это булева формула, потому что навскидку это не понять.
 
* В определении <tex>TAUT</tex> стоит написать, что эта <tex>\phi</tex> — это булева формула, потому что навскидку это не понять.
 
* Косметическая правка: «тогда по лемме 1 <tex>TAUT</tex>…» единица с <tex>TAUT</tex> сливаются, попробуй написать «по лемме (1)…».
 
* Косметическая правка: «тогда по лемме 1 <tex>TAUT</tex>…» единица с <tex>TAUT</tex> сливаются, попробуй написать «по лемме (1)…».
* Псевдокод <tex>check(\phi, i)</tex>, очевидно, неверен. Хотя бы потому что случаи <tex> \phi = 0 </tex> и <tex> \phi = 1 </tex> недостижимы. Во втором псевдокоде та же бага, исправь, после я буду читать дальше.
+
* Второй абзац после второго псевдокода: странная оценка, там (1) может быть неверно максимум 1 раз.
 +
* Последний абзац написан неподробно.
 +
 
 +
== Ох-ох ==
 +
Мне очень не нравится, когда теховская формула разрывается, чтобы вставить в неё русский текст. К сожалению, мне не известно ни одного решения этой проблемы =(. [[Участник:Kirelagin|Кирилл Елагин]] 23:28, 29 апреля 2012 (GST)
 +
 
 +
== Омг ==
 +
 
 +
Где определение coNPC? Что доказываем-то? Доказываем-то по сути эквивалентность двух определений — coNP-C и co-NPC. При использовании второго определения лемма выглядит как бред (я над ней думал очень-очень долго). [[Участник:Kirelagin|Кирилл Елагин]] 01:03, 3 июня 2012 (GST)

Текущая версия на 00:03, 3 июня 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)…».
  • Второй абзац после второго псевдокода: странная оценка, там (1) может быть неверно максимум 1 раз.
  • Последний абзац написан неподробно.

Ох-ох

Мне очень не нравится, когда теховская формула разрывается, чтобы вставить в неё русский текст. К сожалению, мне не известно ни одного решения этой проблемы =(. Кирилл Елагин 23:28, 29 апреля 2012 (GST)

Омг

Где определение coNPC? Что доказываем-то? Доказываем-то по сути эквивалентность двух определений — coNP-C и co-NPC. При использовании второго определения лемма выглядит как бред (я над ней думал очень-очень долго). Кирилл Елагин 01:03, 3 июня 2012 (GST)