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

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

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

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

По-моему, надо пояснить понятие «допускать [math]r_i[/math]». Не очень понятно, что имеется в виду.

В первом куске кода что-то не так с форматированием. И наверное было бы здорово комментарии все выровнить. И return' — это, кажется, что-то вроде yield?

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

Да, return' — это yield. Вроде все поправила.

сказала, что yield, а в статье сделала return o_0. Ну я тебе там в чятике еще написал.