Обсуждение:PCP-система

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

Программа с двумя графами обрывается в самом интересном месте. И чему равно [math]\pi[k][/math], когда соответствующий граф ничему не изоморфен? Дмитрий Шевченко 00:00, 5 июня 2012 (GST)