2FA state complexity of k-Clique? In simple form:


  Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?


Details

Of interest here are $v$-vertex graphs encoded using a sequence of edges, each edge being a pair of distinct vertices from $\{0,1,\dots,v-1\}$.

Suppose $(M_v)$ is a sequence of two-way finite automata (deterministic or nondeterministic), such that $M_v$ recognizes $k$-Clique on $v$-vertex input graphs and has $s(v)$ states.
A general form of the question is then:
Is $s(v) = \Omega(v^k)$?

If $k = k(v) = \omega(1)$ and $s(v) \ge v^{k(v)}$ for infinitely many $v$, then NL ≠ NP.
Less ambitiously, I am therefore stipulating that $k$ is fixed, and the $k=3$ case is the first nontrivial one.

Background

A two-way finite automaton (2FA) is a Turing machine which has no workspace, only a fixed number of internal states, but can move its read-only input head back and forth.
In contrast, the usual kind of finite automaton (1FA) moves its read-only input head in one direction only.
Finite automata can be deterministic (DFA) or nondeterministic (NFA), as well as having one-way or two-way access to their input.

A graph property $Q$ is a subset of graphs.
Let $Q_v$ denote the $v$-vertex graphs with property $Q$.
For every graph property $Q$, the language $Q_v$ can be recognized by a 1DFA with at most $2^{v(v-1)/2}$ states, by using a state for every possible graph and labelling them according to $Q$, and transitions between states labelled by edges.
$Q_v$ is therefore a regular language for any property $Q$.
By the Myhill-Nerode theorem there is then a unique up to isomorphism smallest 1DFA that recognizes $Q_v$.
If this has $2^{s(v)}$ states, then standard blowup bounds yield that a 2FA recognizing $Q_v$ has at least $s(v)^{\Omega(1)}$ states.
So this approach via standard blowup bounds only yields at most a quadratic in $v$ lower bound on the number of states in a 2FA for any $Q_v$ (even when $Q$ is hard or undecidable).

$k$-Clique is the graph property of containing a complete $k$-vertex subgraph.
Recognizing $k$-Clique$_v$ can be done by a 1NFA that first nondeterministically chooses one of $\binom{v}{k}$ different potential $k$-cliques to look for, and then scans the input once, looking for each of the required edges to confirm the clique, and keeping track of these edges using $2^{k(k-1)/2}$ states for each of the different potential cliques.
Such a 1NFA has $\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$ states, where $1 \le c_v \le e$.
When $k$ is fixed, this is $\Theta(v^k)$ states.
Allowing two-way access to the input potentially allows an improvement over this one-way bound.
The question is then asking for $k=3$ whether a 2FA can do better than this 1FA upper bound.

Addendum (2017-04-16): see also a related question for deterministic time and a nice answer covering the best known algorithms.
My question focuses on nonuniform nondeterministic space.
In this context the reduction to matrix multiplication used by the time-efficient algorithms is worse than the brute-force approach.
It seems to me that triangles can be done by a 2FA $A$ with $O(n^2)$ state (n being the number of vertices).

For $k=3$ the idea is as follows:


In phase 1, $A$ chooses some edge $(i,j)$ and stores $(phase 1,i,j)$ in its state
In phase 2 it moves to some edge of the form $(i,m)$ or $(m,i)$ and assumes a state of the form $(phase 2,j,m)$
In phase 3, it checks that there is some edge $(j,m)$ or $(m,j)$ and assume an accepting state if it finds one.


This can actually almost be done in a left to right fashion (then $A$ might nondeterministically decide to go first for $(j,m)$ or $(m,j)$ in phase 2). However, if the 2nd edge comes in the form $(m,i)$, $A$ needs to first read $i$ and then $m$, i.e., a single left-step is needed here. 

This should result in automata with $O(n^{k-1})$ states for $k$-Clique for $k&gt;3$ by first guessing a set $S$ of size $k-3$ and testing, that he nodes of $S$ are pairwise connected by edges and, for each of  i,j,m in the above, checking that they have edges to all nodes in $S$.