Обсуждение:Теорема Ладнера — различия между версиями
Kirelagin (обсуждение | вклад) |
Kirelagin (обсуждение | вклад) (Сам исправил) |
||
| Строка 4: | Строка 4: | ||
Ссылка на NP-полноту SAT'а. | Ссылка на NP-полноту SAT'а. | ||
Ссылка на сведение. | Ссылка на сведение. | ||
| − | |||
| − | |||
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)? | Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)? | ||
| Строка 14: | Строка 12: | ||
Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо. | Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо. | ||
| − | |||
| − | |||
Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо. | Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо. | ||
Версия 13:53, 2 июня 2012
Есть мнение, что эту теорему надо оформить как теорему.
В первой же строке явно просится ссылка на P. Ссылка на NP-полноту SAT'а. Ссылка на сведение.
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…
«названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю…
Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо.
Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо.
Используй обозначение T(программа, вход) — это относится и к началу статьи и к концу.
Что за Т со звездой? Каких шагов время считаем? Ничерта не понятно в последней части. И, ты меня прости, но мне кажется, что если не разбивать по строкам формулы, то читаться будет лучше.
Кирилл Елагин 13:58, 2 июня 2012 (GST)
