В простой форме:
Может ли двусторонний конечный автомат распознавать вершинные графы, содержащие треугольник с состояниями?
Детали
Здесь представляют интерес графы с вершинами, закодированные с использованием последовательности ребер, причем каждое ребро представляет собой пару различных вершин из .
Предположим, что - это последовательность двусторонних конечных автоматов (детерминированных или недетерминированных), такая, что распознает -Clique на входных вершинных графах и имеет состояния. Общая форма вопроса такова: ?
Если и для бесконечного числа , то NL ≠ NP. Менее амбициозно, поэтому я утверждаю, что фиксировано, и случай является первым нетривиальным.
Фон
Двусторонний конечный автомат (2FA) - это машина Тьюринга, у которой нет рабочего пространства, только фиксированное число внутренних состояний, но он может перемещать свою входную головку только для чтения вперед и назад. Напротив, обычный вид конечного автомата (1FA) перемещает свою входную головку только для чтения только в одном направлении. Конечные автоматы могут быть детерминированными (DFA) или недетерминированными (NFA), а также иметь односторонний или двусторонний доступ к их входу.
Свойство графа является подмножеством графов. Пусть обозначим -vertex графы со свойством . Для каждого свойства графа язык может быть распознан 1DFA с максимум состояниями, используя состояние для каждого возможного графа и помечая их в соответствии с , и переходы между состояния помечены ребрами. поэтому является регулярным языком для любого свойства . По теореме Майхилла-Нерода существует единственный наименьший с точностью до изоморфизма 1DFA, который распознает . Если это имеетQ v vQ Q v 2 v ( v - 1 ) / 2 Q Q v Q Q v 2 s ( v ) Q v s ( v ) Ω ( 1 ) v Q v Qсостояния, тогда стандартные границы раздува дают 2FA, распознающий , по крайней мере состояний. Таким образом, этот подход с помощью стандартных границ раздува дает не более квадратичной по нижней границы числа состояний в 2FA для любого (даже когда является жестким или неразрешимым).
K K V -Clique - свойство графа, содержащее полный подграф вершины. Распознавание -Clique может быть выполнено 1NFA, который сначала недетерминистически выбирает один из различных потенциальных -кликов для поиска, а затем сканирует входные данные один раз, просматривая каждый из требуемых ребер для подтверждения клика и отслеживание этих ребер с использованием состояний для каждой из возможных потенциальных клик. Такой 1NFA имеет состояний, где . Когда фиксировано, это2 k ( k - 1 ) / 2 ( v1≤cv≤ekΘ(vk)k=3состояния. Разрешение двустороннего доступа к входу потенциально позволяет улучшить эту одностороннюю границу. Тогда возникает вопрос, при , может ли 2FA работать лучше, чем эта верхняя граница 1FA.
Приложение (2017-04-16): см. Также связанный вопрос для детерминированного времени и хороший ответ, охватывающий самые известные алгоритмы . Мой вопрос посвящен неоднородному недетерминированному пространству. В этом контексте сокращение к матричному умножению, используемому алгоритмами с эффективным использованием времени, хуже, чем метод грубой силы.
источник
Ответы:
Мне кажется, что треугольники могут быть сделаны 2FA с состоянием (n является числом вершин).O ( n 2 )A O(n2)
Для идея заключается в следующем:k=3
На самом деле это практически можно сделать слева направо (тогда может недетерминированным образом решить сначала пойти на или на этапе 2). Однако, если 2-е ребро имеет вид , сначала нужно прочитать а затем , т. Е. Здесь требуется один шаг влево.( j , m ) ( m , j ) ( m , i ) A i mA (j,m) (m,j) (m,i) A i m
Это должно привести к автоматам с состояниями для Клика для , сначала угадав множество размера и проверив, что узлы попарно соединены ребрами и , для каждого из I, J, м выше, проверяя , что они имеют ребра на все узлы в .k k > 3 S k - 3 S SO(nk−1) k k>3 S k−3 S S
источник