Обсуждение:PCP-система — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
Интересует момент <tex>\mathrm{PCP}[0, O(log(n))] = \mathrm{P}</tex>. Да, мы можем сгенерировать все доказательства, но мы же не знаем, какое из них верное — какому из результатов доверять. [[Участник:Shevchen|Дмитрий Шевченко]] 23:58, 4 июня 2012 (GST)
 
Интересует момент <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)
  
 
Программа с двумя графами обрывается в самом интересном месте. [[Участник:Shevchen|Дмитрий Шевченко]] 00:00, 5 июня 2012 (GST)
 
Программа с двумя графами обрывается в самом интересном месте. [[Участник:Shevchen|Дмитрий Шевченко]] 00:00, 5 июня 2012 (GST)
 +
: Это какое же место там самое интересное?
 +
:: То, где ничего не возвращается.
 +
:: UPD: а, похоже, там нет больше случаев. Тогда зачем последний if? [[Участник:Shevchen|Дмитрий Шевченко]] 01:19, 5 июня 2012 (GST)
 +
::: Для наглядности был. Заменил на комментарий.

Текущая версия на 00:32, 5 июня 2012

Интересует момент [math]\mathrm{PCP}[0, O(log(n))] = \mathrm{P}[/math]. Да, мы можем сгенерировать все доказательства, но мы же не знаем, какое из них верное — какому из результатов доверять. Дмитрий Шевченко 23:58, 4 июня 2012 (GST)

У нас случайных битов нет, поэтому на фиксированном доказательстве [math]\pi[/math] [math]V[/math] работает одинаково.
То есть, если была такая цепочка, что [math]V[/math] допустил, то допускаем. Если не было, то не допускаем.
А, ок, я продолбал «для некоторого/любого [math]\pi[/math]». Дмитрий Шевченко 01:19, 5 июня 2012 (GST)

Программа с двумя графами обрывается в самом интересном месте. Дмитрий Шевченко 00:00, 5 июня 2012 (GST)

Это какое же место там самое интересное?
То, где ничего не возвращается.
UPD: а, похоже, там нет больше случаев. Тогда зачем последний if? Дмитрий Шевченко 01:19, 5 июня 2012 (GST)
Для наглядности был. Заменил на комментарий.