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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вторая часть доказательства: Новая тема)
(Странное ограничение)
 
(не показано 7 промежуточных версий 2 участников)
Строка 3: Строка 3:
 
Прочитай, пожалуйста, весь конспект ещё раз, исправь все проблемы согласования и лишние значки типа скобочек. Ставить тире внутри теха — идиотская идея (не только потому что такие тире отвратительно выглядят), а заодно, исправляя это, замени (как минимум) в одном месте тире на дефис. Было бы здорово, если бы ты придумал, как это доказательство записать по-нормальному, чтобы было понятно и можно было спокойно прочитать, потому что иначе это придётся делать мне и я буду не очень доволен. Особенно жутко, конечно, выглядит переход с 0-го на i-й шаг, где сразу же на ровном сыпятся какие-то утверждения про текущее состояние — надо, вероятно, поподробнее инвариант описать. [[Участник:Kirelagin|Кирилл Елагин]] 01:05, 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)
  
 
== Первая часть доказательства ==
 
== Первая часть доказательства ==
Строка 14: Строка 15:
  
 
После описания 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>.<br/>
 +
(Друзья, давайте, всё-таки, будем подписываться! Или, хотя бы, логиниться. -- [[Участник:Kirelagin|Кирилл Елагин]] 23:06, 3 июня 2012 (GST))
 +
 +
: Присоединяюсь к вопросу. «Будем строить <tex>B</tex> так, чтобы <tex>\ldots</tex>» выглядит странным: для <tex>x: |x| = 1</tex> неравенство выполняется всегда. И хочется больше конкретики по поводу «бесконечного числа слов» из последнего предложения теоремы: кто сказал, что <tex>n</tex> будет расти с ростом <tex>i</tex>? Может, мы часто будем удалять слова из <tex>B</tex>. [[Участник:Shevchen|Дмитрий Шевченко]] 19:01, 4 июня 2012 (GST)
 +
 +
Я понимаю, что такое время работы программы на данном входе. Я не понимаю, что такое «программа (не) разрешает такой-то язык за время <tex>2^{n-1}</tex>». [[Участник:Kirelagin|Кирилл Елагин]] 23:06, 3 июня 2012 (GST)
 +
 +
== Мелкие по сравнению с остальным претензии ==
 +
 +
У тебя B написано то курсивным то прямым шрифтом (подсказка: посмотри в степени) (подсказка2: должно быть везде курсивным). [[Участник:Kirelagin|Кирилл Елагин]] 23:08, 3 июня 2012 (GST)
 +
 +
Первое следствие надо удалить, потому что оно есть во втором. Второе следствие надо переписать по-человечески. [[Участник:Kirelagin|Кирилл Елагин]] 23:08, 3 июня 2012 (GST)

Текущая версия на 18:01, 4 июня 2012

Во-первых, тебе не повезло: я думал, какой бы конспект почитать, ткнул наугад и попал в твой. Во-вторых, верни, пожалуйста, на место все знаки препинания особенно точки в концах предложений и что-нибудь в районе списков). В-третьих, использовать википедийные подзаголовки где-то внутри доказательства — плохая идея (и я, честно говоря, совсем не понимаю, что с этим делать). В-четвёртых, 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]B[/math] так, чтобы [math]\ldots[/math]» выглядит странным: для [math]x: |x| = 1[/math] неравенство выполняется всегда. И хочется больше конкретики по поводу «бесконечного числа слов» из последнего предложения теоремы: кто сказал, что [math]n[/math] будет расти с ростом [math]i[/math]? Может, мы часто будем удалять слова из [math]B[/math]. Дмитрий Шевченко 19:01, 4 июня 2012 (GST)

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

Мелкие по сравнению с остальным претензии

У тебя B написано то курсивным то прямым шрифтом (подсказка: посмотри в степени) (подсказка2: должно быть везде курсивным). Кирилл Елагин 23:08, 3 июня 2012 (GST)

Первое следствие надо удалить, потому что оно есть во втором. Второе следствие надо переписать по-человечески. Кирилл Елагин 23:08, 3 июня 2012 (GST)