С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, 191023, Санкт-Петербург, Россия
This preprint was accepted December 20, 2012
АННОТАЦИЯ:
В этой статье мы рассматриваем два типа неклассических систем
доказательств: эвристические системы доказательств и инвариантные системы
доказательств, и приводим нетривиальные примеры таких систем
доказательств. Мы приводим пример распределенной задачи $(Y,D)$, которая
лежит в классе $\rm HeurNP$, но при этом $Y\notin NP$, если $\rm NP\neq coNP$, и $(Y,D)\notin \rm HeurBPP$, если
$(\rm NP, PSamp)\not\subseteq HeurBPP$.
Для языка $L$ и полинома $q$ определим язык $L_q$, который состоит из пар $(x,r)$, где $x$ --- это элемент $L$, а $r$ --- произвольная битовая строка длины
$q(|x|)$. Если $D=\{D_n\}_{n=1}^\infty$ --- это ансамбль распределений на строках,
обозначим $D\times U^q$ --- распределение на парах $(x,r)$, где строка $x$ распределена согласно $D_n$, а
$r$ распределена равномерно среди строк длины $q(n)$. Мы показываем, что для каждого языка $L$ из класса $\rm AM$ существует такой полином $q$,
что для любого распределения $D$ с носителем на дополнении языка $L$, распределенная задача $(L_q, D\times U^q)$ имеет полиномиально
ограниченную эвристическую систему доказательств.
Поскольку язык пар неизоморфных графов $GNI\in \rm AM$, то упомянутый результат применим к этому языку $GNI$.
Мы определяем понятие инвариантных систем доказательств для языка $GNI$,
доказательство в которых остается верным при перестановке вершин графов.
Мы строим $p$-оптимальную инвариантную систему доказательств, т.е.
доказательство в любой другой инвариантной системе может быть
за полиномиальное время переделано в доказательство в этой системе.
©
Ключевые слова:
система доказательств, эвристические вычисления,
p-оптимальная система доказательств
ABSTRACT:
In this paper we consider two types of non-classical proof systems:
heuristic proof systems and invariant proof systems,
and give non-trivial examples of proof systems of this kind.
We give an example of the distributional problem $(Y,D)$
that is in complexity class $\rm HeurNP$ but $Y\notin NP$
if $\rm NP\neq coNP$, and $(Y,D)\notin \rm HeurBPP$
if $(\rm NP, PSamp)\not\subseteq HeurBPP$.
For a language $L$ and a polynomial $q$, define the language
$L_q$ composed of pairs $(x,r)$ where $x$ is an element of $L$
and $r$ is an arbitrary binary string of length $q(|x|)$.
If $D=\{D_n\}_{n=1}^\infty$ is an ensemble of distributions
on strings, $D\times U^q$ signifies the distribution on pairs
$(x,r)$ where $x$ is distributed according to $D_n$ and $r$
is uniformly distributed on strings of length $q(n)$.
We show that for every language $L$ from $\rm AM$ there exists
some polynomial $q$ that for every distribution $D$ concentrated
on the complement of $L$ the distributional problem
$(L_q, D\times U^q)$ has polynomially bounded heuristic proof system.
Since the language composed of all the pairs of non-isomorphic
graphs $GNI$ is in $\rm AM$, the above result is applicable to $GNI$.
We define the notion of invariant proof system for $GNI$,
the proof of such system remains valid under the permutation
of graph vertices. We construct p-optimal invariant proof system,
i.e. every proof of any other invariant proof system is
able to be translated into some proof of this proof system
in polynomial time.
Key words proof system, heuristic computation, p-optimal proof system
[Full text:
Preprint in Russian (.pdf.gz)
Back to all preprints
Back to the Steklov
Institute of Mathematics at St.Petersburg