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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 8: Строка 8:
  
 
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?
 
Про функции не понял. Чем они от машин отличаются? Типа, могут быть невычислимы (тогда надо это явно указать)?
 +
* [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>.
  
 
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…
 
Делимость процентиком не в программах — не очень. Поставь лучше три точки, наверное…

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

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

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

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

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

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

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

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

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

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

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


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