Обсуждение:Теорема Ладнера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сам исправил)
м
 
(не показано 10 промежуточных версий 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] Полиномиальная функция — объект, который пользуется полиномиальной МТ для получения результата из [math]\Sigma^*[/math].

Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…

Done — заменил на модульное сравнение, потому как точки смотрятся плохо.

«названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю…

Done

Определение g — АД. Там ничего не понятно. Серьёзно. Перепиши, чтобы было понятно «если <что>, то <что>». Если хочешь при этом использовать списки, то делай обычные html'ные — вики-разметка не вытянет то, что тебе надо.

Done — надеюсь, стало лучше читаться
Стало хуже читаться, потому что теперь не указано, что последние два пункта — если не выполняется то странное неравенство.
Указал.

Я сверху вынес степень логарифма за скобочки. Не знаю, надо ли это же сделать внизу в доказательстве времени. Если сильно ухудшит читабельность, то не надо.

Done

Используй обозначение T(программа, вход) — это относится и к началу статьи и к концу.

Done

Что за Т со звездой? Каких шагов время считаем? Ничерта не понятно в последней части. И, ты меня прости, но мне кажется, что если не разбивать по строкам формулы, то читаться будет лучше.

Done: выпилил

Название заголовка «корректность алгоритма» — так себе. Формально-то нет тут никакого алгоритма, корректность которого доказывать надо было бы.

Done: добавил слово «алгоритм»
Хитрый.

Кирилл Елагин 13:58, 2 июня 2012 (GST)