INSTANCE: A two-way nondeterministic finite state automaton A over single Alphabet I. QUESTION: Is there an string x (over I) such that A accepts x ?
Since a 2-way NFA with N states, there’s an equivalent nfa with n^(n+1) states. So that’s we get the exponential time from.
I am clear about that, but if I understand correctly the size of the string accepted by the 2Way NFA would still be (in the worst case) polynomial to number of states in the 2Way NFA. Cause if the smallest string accepted was exponential in size, the verification will also take exponential time and thus the problem by definition would not be NP Complete ? Or is there a mistake in this reasoning?