Обсуждение:Классы NC и AC

Теорема

Откуда взялись какие-то семейства о_0? В связи с этим, надо переписать доказательство так, чтобы там не было мути. Кирилл Елагин 01:31, 30 апреля 2012 (GST)

Мне кажется, вместо «схемы» надо писать «логические схемы». Ну просто потому что иначе не понятно, о каких схемах идет речь. Кирилл Елагин 01:31, 30 апреля 2012 (GST)

Совершенно не очевидно, что размер останется полиномиальным. Тем более, что, по-моему, чтобы это понять, надо знать факт про логарифм, который написан дальше. Кирилл Елагин 01:31, 30 апреля 2012 (GST)

Глубина увеличится не «на», а «в», и вообще это надо по-человечески написать. Кирилл Елагин 01:31, 30 апреля 2012 (GST)

Я не понял, почему доказательство теоремы про отношение с P идёт после «тезиса». Оно же от него не зависит, надо бы пораньше написать. Доказательство там тоже мутное в свете каких-то семейств. И надо указать, что равенство — неразрешенная на данный момент задача. Кирилл Елагин 01:31, 30 апреля 2012 (GST)

Тезис, конечно, надо оформить не так, а в отдельном разделе (скажем, «Свзь с параллельными вычислениями» или как-то так) и выглядеть он должен совсем не так. Посмотри, как оформляли другие тезисы (мне лень) — возможно, есть какой-то шаблон. Если шаблона нет, то, наверное, надо его запилить. Кирилл Елагин 01:31, 30 апреля 2012 (GST)