Обсуждение:Теорема Ладнера — различия между версиями
Kirelagin (обсуждение | вклад) |
Shevchen (обсуждение | вклад) м |
||
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
Есть мнение, что эту теорему надо оформить как теорему. | Есть мнение, что эту теорему надо оформить как теорему. | ||
| + | : Done | ||
В первой же строке явно просится ссылка на P. | В первой же строке явно просится ссылка на P. | ||
Ссылка на NP-полноту SAT'а. | Ссылка на NP-полноту SAT'а. | ||
Ссылка на сведение. | Ссылка на сведение. | ||
| − | + | : Done | |
| − | |||
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)? | Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)? | ||
| + | : [http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_P#.D0.A4.D0.BE.D1.80.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5] Полиномиальная функция — объект, который пользуется полиномиальной МТ для получения результата из <tex>\Sigma^*</tex>. | ||
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное… | Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное… | ||
| + | : Done — заменил на модульное сравнение, потому как точки смотрятся плохо. | ||
«названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю… | «названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю… | ||
| + | : Done | ||
Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо. | Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо. | ||
| − | + | : Done — надеюсь, стало лучше читаться | |
| − | + | :: Стало хуже читаться, потому что теперь не указано, что последние два пункта — если не выполняется то странное неравенство. | |
| + | ::: Указал. | ||
Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо. | Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо. | ||
| + | : Done | ||
Используй обозначение T(программа, вход) — это относится и к началу статьи и к концу. | Используй обозначение T(программа, вход) — это относится и к началу статьи и к концу. | ||
| + | : Done | ||
Что за Т со звездой? Каких шагов время считаем? Ничерта не понятно в последней части. И, ты меня прости, но мне кажется, что если не разбивать по строкам формулы, то читаться будет лучше. | Что за Т со звездой? Каких шагов время считаем? Ничерта не понятно в последней части. И, ты меня прости, но мне кажется, что если не разбивать по строкам формулы, то читаться будет лучше. | ||
| + | : Done: выпилил | ||
| + | |||
| + | Название заголовка «корректность алгоритма» — так себе. Формально-то нет тут никакого алгоритма, корректность которого доказывать надо было бы. | ||
| + | : Done: добавил слово «алгоритм» | ||
| + | :: Хитрый. | ||
------------ | ------------ | ||
[[Участник:Kirelagin|Кирилл Елагин]] 13:58, 2 июня 2012 (GST) | [[Участник:Kirelagin|Кирилл Елагин]] 13:58, 2 июня 2012 (GST) | ||
Текущая версия на 15:38, 3 июня 2012
Есть мнение, что эту теорему надо оформить как теорему.
- Done
В первой же строке явно просится ссылка на P. Ссылка на NP-полноту SAT'а. Ссылка на сведение.
- Done
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?
- [1] Полиномиальная функция — объект, который пользуется полиномиальной МТ для получения результата из .
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…
- Done — заменил на модульное сравнение, потому как точки смотрятся плохо.
«названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю…
- Done
Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо.
- Done — надеюсь, стало лучше читаться
- Стало хуже читаться, потому что теперь не указано, что последние два пункта — если не выполняется то странное неравенство.
- Указал.
- Стало хуже читаться, потому что теперь не указано, что последние два пункта — если не выполняется то странное неравенство.
Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо.
- Done
Используй обозначение T(программа, вход) — это относится и к началу статьи и к концу.
- Done
Что за Т со звездой? Каких шагов время считаем? Ничерта не понятно в последней части. И, ты меня прости, но мне кажется, что если не разбивать по строкам формулы, то читаться будет лучше.
- Done: выпилил
Название заголовка «корректность алгоритма» — так себе. Формально-то нет тут никакого алгоритма, корректность которого доказывать надо было бы.
- Done: добавил слово «алгоритм»
- Хитрый.
Кирилл Елагин 13:58, 2 июня 2012 (GST)
