108
правок
Изменения
Нет описания правки
Интересует момент <tex>\mathrm{PCP}[0, O(log(n))] = \mathrm{P}</tex>. Да, мы можем сгенерировать все доказательства, но мы же не знаем, какое из них верное — какому из результатов доверять. [[Участник:Shevchen|Дмитрий Шевченко]] 23:58, 4 июня 2012 (GST)
: У нас случайных битов нет, поэтому на фиксированном доказательстве <tex>\pi</tex> <tex>V</tex> работает одинаково.<br/> То есть, если была такая цепочка, что <tex>V</tex> допустил, то допускаем. Если не было, то не допускаем.
:: А, ок, я продолбал «для некоторого/любого <tex>\pi</tex>». [[Участник:Shevchen|Дмитрий Шевченко]] 01:19, 5 июня 2012 (GST)
Программа с двумя графами обрывается в самом интересном месте. И чему равно <tex>\pi[k[Участник:Shevchen|Дмитрий Шевченко]]</tex>00:00, 5 июня 2012 (GST): Это какое же место там самое интересное?:: То, когда соответствующий граф ничему где ничего не изоморфенвозвращается. :: UPD: а, похоже, там нет больше случаев. Тогда зачем последний if? [[Участник:Shevchen|Дмитрий Шевченко]] 0001:0019, 5 июня 2012 (GST)::: Для наглядности был. Заменил на комментарий.
