Обсуждение:Классы L, NL, coNL. NL-полнота задачи о достижимости — различия между версиями
Kirelagin (обсуждение | вклад) |
Kirelagin (обсуждение | вклад) |
||
| Строка 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
Определеньки надо бы вынести из теорем.
Я, видимо, туплю, но я не понимаю, как …
- А, я нашёл это в самом конце. Такое ощущение, что теорему и лемму нужно разделить. Во-первых, лемма внутри теоремы выглядит просто как-то не очень. Во-вторых, у тебя там всё смешалось и часть доказательства теоремы почему-то доказывается в конце леммы. Ну т.е. я зато, чтобы лемму вынести из теоремы, причем, возможно, надо написать ее после теоремы, а в теореме аккуратно сослаться, что, мол, вот, если мы докажем вот такую вот лемму, то тогда то-то и то-то, а вот лемму мы докажем попозже. И ещё есть ощущение, что у тебя возникнет проблема co-NLC — coNL-C, как у Андрея Дёмина в конспекте. Посмотри там у него, какая ерунда была, и сделай аккуратетько этот момент.
Кирилл Елагин 14:15, 3 июня 2012 (GST)
