Обсуждение:Классы L, NL, coNL. NL-полнота задачи о достижимости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
  
 
Я, видимо, туплю, но я не понимаю, как <tex>\mathrm{\overline{CONN}} \in \mathrm{NL} \Rightarrow \mathrm{NL} = \mathrm{coNL}</tex>…
 
Я, видимо, туплю, но я не понимаю, как <tex>\mathrm{\overline{CONN}} \in \mathrm{NL} \Rightarrow \mathrm{NL} = \mathrm{coNL}</tex>…
 +
: А, я нашёл это в самом конце. Такое ощущение, что теорему и лемму нужно разделить. Во-первых, лемма внутри теоремы выглядит просто как-то не очень. Во-вторых, у тебя там всё смешалось и часть доказательства теоремы почему-то доказывается в конце леммы. Ну т.е. я зато, чтобы лемму вынести из теоремы, причем, возможно, надо написать ее ''после'' теоремы, а в теореме аккуратно сослаться, что, мол, вот, если мы докажем вот такую вот лемму, то тогда то-то и то-то, а вот лемму мы докажем попозже. И ещё есть ощущение, что у тебя возникнет проблема co-NLC — coNL-C, как у Андрея Дёмина в конспекте. Посмотри там у него, какая ерунда была, и сделай аккуратетько этот момент.
  
 
[[Участник:Kirelagin|Кирилл Елагин]] 14:15, 3 июня 2012 (GST)
 
[[Участник:Kirelagin|Кирилл Елагин]] 14:15, 3 июня 2012 (GST)

Версия 13:18, 3 июня 2012

Определеньки надо бы вынести из теорем.

Я, видимо, туплю, но я не понимаю, как [math]\mathrm{\overline{CONN}} \in \mathrm{NL} \Rightarrow \mathrm{NL} = \mathrm{coNL}[/math]

А, я нашёл это в самом конце. Такое ощущение, что теорему и лемму нужно разделить. Во-первых, лемма внутри теоремы выглядит просто как-то не очень. Во-вторых, у тебя там всё смешалось и часть доказательства теоремы почему-то доказывается в конце леммы. Ну т.е. я зато, чтобы лемму вынести из теоремы, причем, возможно, надо написать ее после теоремы, а в теореме аккуратно сослаться, что, мол, вот, если мы докажем вот такую вот лемму, то тогда то-то и то-то, а вот лемму мы докажем попозже. И ещё есть ощущение, что у тебя возникнет проблема co-NLC — coNL-C, как у Андрея Дёмина в конспекте. Посмотри там у него, какая ерунда была, и сделай аккуратетько этот момент.

Кирилл Елагин 14:15, 3 июня 2012 (GST)