2FA заявите о сложности k-Clique?

15

В простой форме:

Может ли двусторонний конечный автомат распознавать вершинные графы, содержащие треугольник с состояниями?vo(v3)

Детали

Здесь представляют интерес графы с вершинами, закодированные с использованием последовательности ребер, причем каждое ребро представляет собой пару различных вершин из .v{0,1,,v1}

Предположим, что - это последовательность двусторонних конечных автоматов (детерминированных или недетерминированных), такая, что распознает -Clique на входных вершинных графах и имеет состояния. Общая форма вопроса такова: ?(Mv)Mvkvs(v)s(v)=Ω(vk)

Если и для бесконечного числа , то NL ≠ NP. Менее амбициозно, поэтому я утверждаю, что фиксировано, и случай является первым нетривиальным.k=k(v)=ω(1)s(v)vk(v)vkk=3

Фон

Двусторонний конечный автомат (2FA) - это машина Тьюринга, у которой нет рабочего пространства, только фиксированное число внутренних состояний, но он может перемещать свою входную головку только для чтения вперед и назад. Напротив, обычный вид конечного автомата (1FA) перемещает свою входную головку только для чтения только в одном направлении. Конечные автоматы могут быть детерминированными (DFA) или недетерминированными (NFA), а также иметь односторонний или двусторонний доступ к их входу.

Свойство графа является подмножеством графов. Пусть обозначим -vertex графы со свойством . Для каждого свойства графа язык может быть распознан 1DFA с максимум состояниями, используя состояние для каждого возможного графа и помечая их в соответствии с , и переходы между состояния помечены ребрами. поэтому является регулярным языком для любого свойства . По теореме Майхилла-Нерода существует единственный наименьший с точностью до изоморфизма 1DFA, который распознает . Если это имеетQ v vQQvvQ Q v 2 v ( v - 1 ) / 2 Q Q v Q Q v 2 s ( v ) Q v s ( v ) Ω ( 1 ) v Q v QQQQv2v(v1)/2QQvQQv2s(v)состояния, тогда стандартные границы раздува дают 2FA, распознающий , по крайней мере состояний. Таким образом, этот подход с помощью стандартных границ раздува дает не более квадратичной по нижней границы числа состояний в 2FA для любого (даже когда является жестким или неразрешимым).Qvs(v)Ω(1)vQvQ

K K Vk -Clique - свойство графа, содержащее полный подграф вершины. Распознавание -Clique может быть выполнено 1NFA, который сначала недетерминистически выбирает один из различных потенциальных -кликов для поиска, а затем сканирует входные данные один раз, просматривая каждый из требуемых ребер для подтверждения клика и отслеживание этих ребер с использованием состояний для каждой из возможных потенциальных клик. Такой 1NFA имеет состояний, где . Когда фиксировано, этоkkv(vk)2 k ( k - 1 ) / 2 ( vk2k(k1)/21cvekΘ(vk)k=3(vk)2k(k1)/2=(cv2(k1)/2/k)k.vk1cvekΘ(vk)состояния. Разрешение двустороннего доступа к входу потенциально позволяет улучшить эту одностороннюю границу. Тогда возникает вопрос, при , может ли 2FA работать лучше, чем эта верхняя граница 1FA.k=3

Приложение (2017-04-16): см. Также связанный вопрос для детерминированного времени и хороший ответ, охватывающий самые известные алгоритмы . Мой вопрос посвящен неоднородному недетерминированному пространству. В этом контексте сокращение к матричному умножению, используемому алгоритмами с эффективным использованием времени, хуже, чем метод грубой силы.

Андраш Саламон
источник
Мне очень нравятся эти вопросы! Спасибо, что поделились этим! :)
Майкл Вехар

Ответы:

7

Мне кажется, что треугольники могут быть сделаны 2FA с состоянием (n является числом вершин).O ( n 2 )AO(n2)

Для идея заключается в следующем:k=3

  1. На этапе 1 выбирает некоторое ребро и сохраняет в своем состоянии.( i , j ) ( p h a s e 1 , i , j )A(i,j)(phase1,i,j)
  2. В фазе 2 он перемещается к некоторому ребру формы или и принимает состояние формы( m , i ) ( p h a s e 2 , j , m )(i,m)(m,i)(phase2,j,m)
  3. На этапе 3 он проверяет наличие некоторого ребра или и принимает принимающее состояние, если находит его.( m , j )(j,m)(m,j)

На самом деле это практически можно сделать слева направо (тогда может недетерминированным образом решить сначала пойти на или на этапе 2). Однако, если 2-е ребро имеет вид , сначала нужно прочитать а затем , т. Е. Здесь требуется один шаг влево.( j , m ) ( m , j ) ( m , i ) A i mA(j,m)(m,j)(m,i)Aim

Это должно привести к автоматам с состояниями для Клика для , сначала угадав множество размера и проверив, что узлы попарно соединены ребрами и , для каждого из I, J, м выше, проверяя , что они имеют ребра на все узлы в .k k > 3 S k - 3 S SO(nk1)kk>3Sk3SS

Томас С
источник
Я не понимаю, как это ? Три вершины отслеживаются. i , j , mO(n2)i,j,m
Андрас Саламон
Только два одновременно. Чтение на этапе 2 выполняется в два перехода. При чтении , основном переходит от (фаза 1, i, j) к (фаза 1a, i, j) (указывая, что он только что видел ) и на следующем шаге в (фаза 2, j, m). На этом этапе это делается с , поскольку он уже видел и и только необходимо проверить. i A i i ( i , j ) ( i , m ) ( j , m )(i,m)iAii(i,j)(i,m)(j,m)
Томас С
Если число ребер и вершин примерно одинаково, то я думаю, что это работает нормально, но интересный случай, когда . Другими словами, я думаю, что ваш подход использует по крайней мере состояний. v ee=Ω(v2)ve
Майкл Вехар
1
Я думаю, вы правы. Если вход дан в хорошем формате, это работает. :)
Майкл Вехар
1
@Marzio: нет, это говорит (нет, это говорит детерминированный или недетерминированный)
Томас С.