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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 
Есть мнение, что эту теорему надо оформить как теорему.
 
Есть мнение, что эту теорему надо оформить как теорему.
Done --[[Участник:Shevchen|Дмитрий Шевченко]] 13:46, 3 июня 2012 (GST)
+
* Done --[[Участник:Shevchen|Дмитрий Шевченко]] 13:46, 3 июня 2012 (GST)
  
 
В первой же строке явно просится ссылка на P.
 
В первой же строке явно просится ссылка на P.
 
Ссылка на NP-полноту SAT'а.
 
Ссылка на NP-полноту SAT'а.
 
Ссылка на сведение.
 
Ссылка на сведение.
 +
* Done --[[Участник:Shevchen|Дмитрий Шевченко]] 13:57, 3 июня 2012 (GST)
  
 
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?
 
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?

Версия 12:57, 3 июня 2012

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

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

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

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

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

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

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

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

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


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