Обсуждение:Теорема Бейкера — Гилла — Соловэя — различия между версиями
Kirelagin (обсуждение | вклад) (Новая страница: «Во-первых, тебе не повезло: я думал, какой бы конспект почитать, ткнул наугад и попал в тво...») |
Shevchen (обсуждение | вклад) (→Странное ограничение) |
||
(не показано 11 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
Во-первых, тебе не повезло: я думал, какой бы конспект почитать, ткнул наугад и попал в твой. Во-вторых, верни, пожалуйста, на место все знаки препинания особенно точки в концах предложений и что-нибудь в районе списков). В-третьих, использовать википедийные подзаголовки где-то внутри доказательства — плохая идея (и я, честно говоря, совсем не понимаю, что с этим делать). В-четвёртых, TQBF не PS-полная, а PS-полный. А теперь я буду читать статью. [[Участник:Kirelagin|Кирилл Елагин]] 00:55, 24 апреля 2012 (GST) | Во-первых, тебе не повезло: я думал, какой бы конспект почитать, ткнул наугад и попал в твой. Во-вторых, верни, пожалуйста, на место все знаки препинания особенно точки в концах предложений и что-нибудь в районе списков). В-третьих, использовать википедийные подзаголовки где-то внутри доказательства — плохая идея (и я, честно говоря, совсем не понимаю, что с этим делать). В-четвёртых, 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>.<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)
Странное ограничение
Я правильно понимаю, что на
(Друзья, давайте, всё-таки, будем подписываться! Или, хотя бы, логиниться. -- Кирилл Елагин 23:06, 3 июня 2012 (GST))
- Присоединяюсь к вопросу. «Будем строить Дмитрий Шевченко 19:01, 4 июня 2012 (GST) так, чтобы » выглядит странным: для неравенство выполняется всегда. И хочется больше конкретики по поводу «бесконечного числа слов» из последнего предложения теоремы: кто сказал, что будет расти с ростом ? Может, мы часто будем удалять слова из .
Я понимаю, что такое время работы программы на данном входе. Я не понимаю, что такое «программа (не) разрешает такой-то язык за время Кирилл Елагин 23:06, 3 июня 2012 (GST)
».Мелкие по сравнению с остальным претензии
У тебя B написано то курсивным то прямым шрифтом (подсказка: посмотри в степени) (подсказка2: должно быть везде курсивным). Кирилл Елагин 23:08, 3 июня 2012 (GST)
Первое следствие надо удалить, потому что оно есть во втором. Второе следствие надо переписать по-человечески. Кирилл Елагин 23:08, 3 июня 2012 (GST)