TY - JOUR

T1 - On an optimal randomized acceptor for graph nonisomorphism

AU - Hirsch, Edward A.

AU - Itsykson, Dmitry

PY - 2012/2/28

Y1 - 2012/2/28

N2 - An acceptor for a language L is an algorithm that accepts every input in L and does not stop on every input not in L. An acceptor Opt for a language L is called optimal if for every acceptor A for this language there exists polynomial pA such that for every xεL, the running time timeOpt(x) of Opt on x is bounded by pA( timeA(x)+|x|) for every xεL. (Note that the comparison of the running time is done pointwise, i.e., for every word of the language.) The existence of optimal acceptors is an important open question equivalent to the existence of p-optimal proof systems for many important languages (Krajíček and Pudlák, 1989; Sadowski, 1999; Messner, 1999 [9,13,11]). Yet no nontrivial examples of languages in NPco-NP having optimal acceptors are known. In this short note we construct a randomized acceptor for graph nonisomorphism that is optimal up to permutations of the vertices of the input graphs, i.e., its running time on a pair of graphs ( G1, G2) is at most polynomially larger than the maximum (in fact, even the median) of the running time of any other acceptor taken over all permuted pairs ( π1( G1), π2( G2)). One possible motivation is the (pointwise) optimality in the class of acceptors based on graph invariants where the time needed to compute an invariant does not depend much on the representation of the input pair of nonisomorphic graphs. In fact, our acceptor remains optimal even if the running time is compared to the average-case running time over all permuted pairs. We introduce a natural notion of average-case optimality (not depending on the language of graph nonisomorphism) and show that our acceptor remains average-case optimal for any probability distribution on the inputs that respects permutations of vertices.

AB - An acceptor for a language L is an algorithm that accepts every input in L and does not stop on every input not in L. An acceptor Opt for a language L is called optimal if for every acceptor A for this language there exists polynomial pA such that for every xεL, the running time timeOpt(x) of Opt on x is bounded by pA( timeA(x)+|x|) for every xεL. (Note that the comparison of the running time is done pointwise, i.e., for every word of the language.) The existence of optimal acceptors is an important open question equivalent to the existence of p-optimal proof systems for many important languages (Krajíček and Pudlák, 1989; Sadowski, 1999; Messner, 1999 [9,13,11]). Yet no nontrivial examples of languages in NPco-NP having optimal acceptors are known. In this short note we construct a randomized acceptor for graph nonisomorphism that is optimal up to permutations of the vertices of the input graphs, i.e., its running time on a pair of graphs ( G1, G2) is at most polynomially larger than the maximum (in fact, even the median) of the running time of any other acceptor taken over all permuted pairs ( π1( G1), π2( G2)). One possible motivation is the (pointwise) optimality in the class of acceptors based on graph invariants where the time needed to compute an invariant does not depend much on the representation of the input pair of nonisomorphic graphs. In fact, our acceptor remains optimal even if the running time is compared to the average-case running time over all permuted pairs. We introduce a natural notion of average-case optimality (not depending on the language of graph nonisomorphism) and show that our acceptor remains average-case optimal for any probability distribution on the inputs that respects permutations of vertices.

KW - Computational complexity

KW - Graph isomorphism

KW - Optimal algorithm

UR - http://www.scopus.com/inward/record.url?scp=84455170919&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2011.11.013

DO - 10.1016/j.ipl.2011.11.013

M3 - Article

AN - SCOPUS:84455170919

VL - 112

SP - 166

EP - 171

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -