2FA complejidad del estado de k-Clique?

En forma simple:

¿Puede un autómata finito bidireccional reconocer gráficos vértice que contienen un triángulo con estados ?$v$$o(v^3)$

Detalles

Aquí son de interés los gráficos vértice codificados usando una secuencia de aristas, cada arista es un par de vértices distintos de .$v$$\{0,1,\dots,v-1\}$

Supongamos que es una secuencia de autómatas finitos bidireccionales (deterministas o no deterministas), de modo que reconoce -Clique en los gráficos de entrada -vertex y tiene estados . Una forma general de la pregunta es entonces: ¿Es ?$(M_v)$$M_v$$k$$v$$s(v)$$s(v) = \Omega(v^k)$

Si $k = k(v) = \omega(1)$ y $s(v) \ge v^{k(v)}$ para infinitamente $v$ , entonces NL ≠ NP. Menos ambicioso, por lo tanto, estipulo que $k$ es fijo, y el caso $k=3$ es el primero no trivial.

Antecedentes

Un autómata finito bidireccional (2FA) es una máquina de Turing que no tiene espacio de trabajo, solo un número fijo de estados internos, pero puede mover su cabezal de entrada de solo lectura de un lado a otro. En contraste, el tipo habitual de autómata finito (1FA) mueve su cabezal de entrada de solo lectura en una sola dirección. Los autómatas finitos pueden ser deterministas (DFA) o no deterministas (NFA), además de tener acceso unidireccional o bidireccional a su entrada.

Una propiedad de gráfico $Q$ es un subconjunto de gráficos. Deje $Q_v$ denotan la $v$ gráficos -vertex con bienes $Q$ . Para cada propiedad de gráfico $Q$ , el lenguaje $Q_v$ puede ser reconocido por un 1DFA con un máximo de $2^{v(v-1)/2}$ estados, utilizando un estado para cada gráfico posible y etiquetándolos de acuerdo con $Q$ , y transiciones entre estados etiquetados por bordes. $Q_v$ es por lo tanto un lenguaje regular para cualquier propiedad $Q$. Según el teorema de Myhill-Nerode, existe un único 1DFA hasta el isomorfismo más pequeño que reconoce $Q_v$ . Si esto tiene $2^{s(v)}$ estados, entonces los límites de expansión estándar producen que un 2FA que reconoce $Q_v$ tiene al menos $s(v)^{\Omega(1)}$ estados. Por lo tanto, este enfoque a través de límites de expansión estándar solo produce como máximo un límite inferior cuadrático en $v$ en el número de estados en un 2FA para cualquier $Q_v$ (incluso cuando $Q$ es difícil o indecidible).

-Clique es la propiedad gráfica de contener unsubgrafo k -vertexcompleto. El reconocimiento de k -Clique v puede ser realizado por un 1NFA que primero elige de forma no determinista una dediferentescliquespotencialespara buscar, y luego escanea la entrada una vez, buscando cada uno de los bordes requeridos para confirmar la camarilla, y hacer un seguimiento de estos bordes usandoestados para cada una de las diferentes camarillas potenciales. Tal 1NFA tieneestados, donde. Cuandoes fijo, esto es$k$$k$$k$$_v$$\binom{v}{k}$$k$$2^{k(k-1)/2}$$\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$$1 \le c_v \le e$$k$$\Theta(v^k)$estados. Permitir el acceso bidireccional a la entrada potencialmente permite una mejora sobre este límite unidireccional. La pregunta es preguntar por si un 2FA puede hacerlo mejor que este límite superior de 1FA.$k=3$

Anexo (16/04/2017): vea también una pregunta relacionada para el tiempo determinista y una buena respuesta que cubre los algoritmos más conocidos . Mi pregunta se centra en el espacio no uniforme no determinista. En este contexto, la reducción a la multiplicación de matrices utilizada por los algoritmos de tiempo eficiente es peor que el enfoque de fuerza bruta.

Me parece que los triángulos se pueden hacer con un 2FA con estado (n es el número de vértices).$A$$O(n^2)$

Para la idea es la siguiente:$k=3$

1. En la fase 1, elige algún borde y almacena en su estado$A$$(i,j)$$(phase 1,i,j)$
2. En la fase 2 se mueve a algún borde de la forma o y asume un estado de la forma$(i,m)$$(m,i)$$(phase 2,j,m)$
3. En la fase 3, verifica que haya algún borde o y asume un estado de aceptación si encuentra uno.$(j,m)$$(m,j)$

En realidad, esto casi se puede hacer de izquierda a derecha (entonces podría decidir de manera no determinista ir primero a o en la fase 2). Sin embargo, si el segundo borde tiene la forma , necesita leer primero luego , es decir, aquí se necesita un solo paso a la izquierda.$A$$(j,m)$$(m,j)$$(m,i)$$A$$i$$m$

Esto debería resultar en autómatas con estados para -Clique para adivinando primero un conjunto de tamaño y probando que los nodos de están conectados en pares por bordes y , para cada uno de i, j, m en el anterior, la comprobación de que tienen bordes a todos los nodos de .$O(n^{k-1})$$k$$k>3$$S$$k-3$$S$$S$