1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

For a problem to be in NP, there needs to be a polynomial time verifier for it. This polynomial time verifier need not be the "obvious" one. Ruling out one specific verifier doesn't prove that the problem is not in NP.

For a problem to be NP-complete, it needs to satisfy two properties: (i) it needs to be in NP, and (ii) it need to be NP-hard. You can look these concepts up in many sources. In particular, the fact that there is some natural exponential time algorithm for a problem doesn't imply that it is NP-complete, though it is true that every problem in NP has an exponential time algorithm.

Unfortunately I am not versed well enough in two-way automata to answer your specific question, but my comments above imply that the answer doesn't necessarily have a direct bearing on whether the emptiness problem for 2NFAs is NP-complete or not (or even in NP or not).

Improve this answer
$\endgroup$
9
  • $\begingroup$ Much thanks. The problem IS NP-Complete. The Reference (G&J): [AL2] TWO-WAY FINITE STATE AUTOMATON NON-EMPTINESS (*) - "PSPACE-complete, even if |I|=2 and A is deterministic. If |l| = l the general problem is NP-complete " So if they state its NP-Complete the string (case |l| = 1), if at all there is a string that is accepted by a given 2 Way NFA (i.e. the Automaton is non-empty), by definition of NP, it would always mean that the length of string would be polynomial in size w.r.t. the Size of Automaton (i.e. the number of states in it) in the 'worst case' ? $\endgroup$
    – TheoryQuest1
    Commented May 31, 2017 at 18:44
  • 1
    $\begingroup$ No. It just means that there is some way to verify (given a witness) in polynomial time that the language accepted by a 2NFA over a unary alphabet is non-empty. It doesn't mean that a particular algorithm (given a string as witness, verify that the 2NFA accepts it) works in polynomial time. It just means that some algorithm does. $\endgroup$
    – Yuval Filmus
    Commented May 31, 2017 at 18:55
  • $\begingroup$ understood. The paper itself (mentioned in G&J [AL2]) is a paid one and i don't have access to it. Thus, couldn't see the verifier part and how they verify. $\endgroup$
    – TheoryQuest1
    Commented May 31, 2017 at 19:04
  • $\begingroup$ Prof. I am still struggling with this. If the witness is the string (exponential in length) then even the reading of it will take exponential time. So that is out of question. But, I don't see another way to represent a unary string such that the witness (exactly corresponding to it) is polynomial length and is verifiable? $\endgroup$
    – TheoryQuest1
    Commented Jun 1, 2017 at 7:37
  • $\begingroup$ Sometimes the fact that a problem is in NP is not trivial. I suggest taking a look at the paper. $\endgroup$
    – Yuval Filmus
    Commented Jun 1, 2017 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.