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

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

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

Ну в основном все поправил. Вторая часть доказательства вообще не самая ясная в целом. Там как такого инварианта нет, а мы строим множество с выполнением этого некоторого инварианта. По-моему, я это более-менее ясно написал в конспекте

Научись пользоваться страницами обсуждений. И вообще довольно грустно, что ты забил на моё предложение перечитать конспект ещё раз. Да мне даже одно тире из теха пришлось самому вытащить! Кирилл Елагин 00:19, 30 апреля 2012 (GST)

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

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

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

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

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

Последствия

Из этой теоремы делаются очень глубокие и важные выводы. Про них тоже обязательно надо написать.

«который использует операции релятивизации» — чё это за бредятина? Кирилл Елагин 18:40, 7 мая 2012 (GST)

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

Я правильно понимаю, что на [math]i[/math]-ом шаге [math]n[/math] не зависит от [math]M_i[/math]? Тогда я не понимаю: что плохого в том, что машина [math]M_i[/math] не разрешает слово [math]1^n[/math] за [math]2^{n - 1}[/math] шагов, потому как временной полином для этой машины вполне может выглядеть как: [math]p(k) = 2^n k [/math].
(Друзья, давайте, всё-таки, будем подписываться! Или, хотя бы, логиниться. -- Кирилл Елагин 23:06, 3 июня 2012 (GST))

Я понимаю, что такое время работы программы на данном входе. Я не понимаю, что такое «программа (не) разрешает такой-то язык за время [math]2^{n-1}[/math]». Кирилл Елагин 23:06, 3 июня 2012 (GST)