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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 11: Строка 11:
  
 
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…
 
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…
 +
* Done — заменил на модульное сравнение, потому как точки смотрятся плохо. --[[Участник:Shevchen|Дмитрий Шевченко]] 14:27, 3 июня 2012 (GST)
  
 
«названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю…
 
«названных свойства» — буэ. Указанных,требуемых, перечисленных, не знаю…

Версия 13:27, 3 июня 2012

Есть мнение, что эту теорему надо оформить как теорему.

В первой же строке явно просится ссылка на P. Ссылка на NP-полноту SAT'а. Ссылка на сведение.

Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?

  • [1] Полиномиальная функция — объект, который пользуется полиномиальной МТ для получения результата из [math]\Sigma^*[/math].

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

  • Done — заменил на модульное сравнение, потому как точки смотрятся плохо. --Дмитрий Шевченко 14:27, 3 июня 2012 (GST)

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

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

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

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

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


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