Викиконспекты - Вклад участника [ru]

Обсуждение:Теорема Бейкера — Гилла — Соловэя

2012-06-02T10:47:30Z

178.178.28.244: /* Странное ограничение */ period

Во-первых, тебе не повезло: я думал, какой бы конспект почитать, ткнул наугад и попал в твой. Во-вторых, верни, пожалуйста, на место все знаки препинания особенно точки в концах предложений и что-нибудь в районе списков). В-третьих, использовать википедийные подзаголовки где-то внутри доказательства — плохая идея (и я, честно говоря, совсем не понимаю, что с этим делать). В-четвёртых, TQBF не PS-полная, а PS-полный. А теперь я буду читать статью. [[Участник:Kirelagin|Кирилл Елагин]] 00:55, 24 апреля 2012 (GST)

Прочитай, пожалуйста, весь конспект ещё раз, исправь все проблемы согласования и лишние значки типа скобочек. Ставить тире внутри теха — идиотская идея (не только потому что такие тире отвратительно выглядят), а заодно, исправляя это, замени (как минимум) в одном месте тире на дефис. Было бы здорово, если бы ты придумал, как это доказательство записать по-нормальному, чтобы было понятно и можно было спокойно прочитать, потому что иначе это придётся делать мне и я буду не очень доволен. Особенно жутко, конечно, выглядит переход с 0-го на i-й шаг, где сразу же на ровном сыпятся какие-то утверждения про текущее состояние — надо, вероятно, поподробнее инвариант описать. [[Участник:Kirelagin|Кирилл Елагин]] 01:05, 24 апреля 2012 (GST)

: Ну в основном все поправил. Вторая часть доказательства вообще не самая ясная в целом. Там как такого инварианта нет, а мы строим множество с выполнением этого некоторого инварианта. По-моему, я это более-менее ясно написал в конспекте
:: [http://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B_%D0%BE%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B9 Научись пользоваться страницами обсуждений]. И вообще довольно грустно, что ты забил на моё предложение перечитать конспект ещё раз. Да мне даже одно тире из теха пришлось самому вытащить! [[Участник:Kirelagin|Кирилл Елагин]] 00:19, 30 апреля 2012 (GST)

== Первая часть доказательства ==

Во втором утверждении, формально, написана неправда. Надо написать то же самое, но корректно.

== Вторая часть доказательства ==

В описании i-го шага прям черным по белому написано «конечное множество слов», но, блин, это вообще ниоткуа не следует (на момент прочтения) — это я и имел в виду, когда говорил про инварианты.

После описания i-го шага начинается полный трэш и с точки зрения орфографии, и с согласованием. И со смыслом тоже какая-то беда.

== Последствия ==

Из этой теоремы делаются очень глубокие и важные выводы. Про них тоже обязательно надо написать.
: «который использует операции релятивизации» — чё это за бредятина? [[Участник:Kirelagin|Кирилл Елагин]] 18:40, 7 мая 2012 (GST)

== Странное ограничение ==

Я правильно понимаю, что на <tex>i</tex>-ом шаге <tex>n</tex> не зависит от <tex>M_i</tex>? Тогда я не понимаю: что плохого в том, что машина <tex>M_i</tex> не разрешает слово <tex>1^n</tex> за <tex>2^{n - 1}</tex> шагов, потому как временной полином для этой машины вполне может выглядеть как:

<tex>p(k) = 2^n k </tex>.

Обсуждение:Теорема Бейкера — Гилла — Соловэя

2012-06-02T10:46:51Z

178.178.28.244: /* Странное ограничение */ Новая тема