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?

Improve this question
$\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$
    – Benjamin Steinberg
    Commented 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$
    – TheoryQuest1
    Commented 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$
    – Benjamin Steinberg
    Commented 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$
    – TheoryQuest1
    Commented Aug 17, 2016 at 13:44
  • $\begingroup$ How does that contradict what I said $\endgroup$
    – Benjamin Steinberg
    Commented Aug 17, 2016 at 15:05

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – TheoryQuest1
    Commented 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$
    – TheoryQuest1
    Commented 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$
    – Narad Rampersad
    Commented Aug 18, 2016 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .