On an optimal randomized acceptor for graph nonisomorphism

Edward A. Hirsch, Dmitry Itsykson

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)166-171
Число страниц6
ЖурналInformation Processing Letters
Том112
Номер выпуска5
DOI
СостояниеОпубликовано - 28 фев 2012

Предметные области Scopus

  • Теоретические компьютерные науки
  • Обработка сигналов
  • Информационные системы
  • Прикладные компьютерные науки

Fingerprint Подробные сведения о темах исследования «On an optimal randomized acceptor for graph nonisomorphism». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать