1
$\begingroup$

Given two Nondeterministic Finite State Automaton (A, B).

Q. Do the two recognize different languages?

The Problem is NPComplete if the language has a single alphabet {1}. But PSPACE Complete if the size of the alphabet is 2 or more. Thus its PSPACE Complete for alphabet {0, 1}.

I am perfectly clear with the language being NPComplete (the string that is not part of A but is of B can be the certificate of inequivalence in this case), but I am not sure why would the language be PSPACE complete for larger Alphabet? Why won't the same logic apply?

$\endgroup$
6
  • $\begingroup$ Checking if an non deterministic automation accepts all strings is PSPACE compete. The issue is determinizing an automation is a big blowup $\endgroup$ Aug 17, 2016 at 13:19
  • $\begingroup$ Much thanks. "Checking if an non deterministic automation accepts all strings is PSPACE compete." I think that part is just the definition stated. I want to understand what changes when the no. of alphabets change. Why can't we do the same for {1, 0} what we did for {1}. What limits us which does not in the {1} case. $\endgroup$ Aug 17, 2016 at 13:22
  • $\begingroup$ Over a 1-letter alphabet you can transform things into integer programming. I guess that's how they may do it. $\endgroup$ Aug 17, 2016 at 13:40
  • $\begingroup$ I think that might not be correct. Because Integer Programming over {0,1} is one of Dr. Karp's original NPComplete problems. $\endgroup$ Aug 17, 2016 at 13:44
  • $\begingroup$ How does that contradict what I said $\endgroup$ Aug 17, 2016 at 15:05

1 Answer 1

5
$\begingroup$

Suppose you want to know if an n-state unary NFA fails to accept all strings. If it rejects a string, it rejects one of length $m < 2^n$ (Why? Hint: determinize the NFA via the subset construction.) The "certificate" then, is $m$, which can be written down in $n$ bits. Actually verifying that the NFA does not accept $1^m$ is not completely trivial, but can be done in polynomial time (Hint: let $A$ be the adjacency matrix of the graph of the NFA and compute $A^m$ by repeated squaring (using Boolean arithmetic).). The argument fails for a binary alphabet because now the "certificate" is the entire length-$m$ binary string (not just $m$), which could potentially be as large as $2^n-1$. It is again not entirely trivial to show how to find and verify that this string is rejected in PSPACE, but it can be done.

$\endgroup$
3
  • $\begingroup$ thanks. i somewhat got the basic of the argument: In case of unary alphabet, the essence is convert exponential unary string to binary which leads to polynomial length certificate. This certificate could then be checked in P time (i am still unclear how despite the hint). This process isn't possible in binary alphabet. Here in i am lost. doubts is as follows: 1. How can one find/check an exponential length binary string in PSPACE in case of DTM. This was the part I was confused about. Some references (for beginners) would be helpful regarding this specific prob. $\endgroup$ Aug 17, 2016 at 16:02
  • $\begingroup$ Moreover, if the string size is exponential, haven't we proved that PSPACE is strictly greater than NP. $\endgroup$ Aug 17, 2016 at 16:35
  • 1
    $\begingroup$ The key to finding and checking an an exponential length binary string in PSPACE is to apply Savitch's Theorem, which states that NPSPACE = PSPACE. So you are allowed to use non-determinism here. A good reference for this material would be J. Shallit, A Second Course in Formal Languages and Automata Theory (Section 6.7), Cambridge 2009. $\endgroup$ Aug 18, 2016 at 14:41

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.