World's most popular travel blog for travel bloggers.

# [Answers] $\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$

, ,
Problem Detail:

Hello for a homework I have to show that deciding whether a regex over $\Sigma = \{0,1\}$ descibes $\Sigma^*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).

The thing which irrs me is that I think this problem is in $\mathsf{P}$.

Here is my argumentation:

Let $R$ be a regex, then we have $$L(R) = \{0,1\}^* \Leftrightarrow \overline{L(R)} = \varnothing$$

Given $R$ we can consruct an NFA with $\epsilon$ moves for $L(R)$ in poly. time; eliminating the $\epsilon$ moves (again poly. time: $O(|Q| \cdot |\delta| \cdot |\Sigma|)$) we obtain an NFA $M$.

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline {L(R)}$, whose emptiness we can check with a BFS (again in poly. time).

$\leadsto \mathsf{RegExpEq_{*}} \in \mathsf{P}$

Where does my argumentation shatter? If both my argumentation and the question is correct, then $\mathsf{P} = \mathsf{coNP}$ which seems highly doubtful.

#### Answered By : Untitled

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline{L(R)}$.

Well, that's not true. You won't get $\overline{L(R)}$. That would have happened if $M$ was a DFA, rather than a NFA. So you have to first convert $M$ to $M'$ which is a DFA, but then you would have to spend an exponential time there.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12296

3.2K people like this