Question

For a cnf-formula $\mathbf{\varnothing }$ with $\mathit{m}$ variables and $\mathit{c}$clauses $\mathit{O}\left(cm\right)$ , show that you can construct in polynomial time an NFA with states that accept all nonsatisfying assignments, represented as Boolean strings of length $\mathit{m}$. Conclude that $\mathbf{\text{P≠NP}}$ implies that NFAs cannot be minimized in polynomial time.

Short answer

It has been concluded that $\text{P}\ne \text{NP}$ implies that NFAs cannot be minimized in polynomial time.

Step-by-step solution

Step-1: Nondeterministic Finite Automaton

The acronym NFA stands for Nondeterministic Finite Automaton. If there are multiple possible transitions from one state on the same input symbol, a Finite Automata FA is said to be non-deterministic.

Step-2: CNF formula

Build an NFA $N$on input $\varphi$that chooses one of the $c$clauses nondeterministically and reads input length $m$, accepting if clause is not satisfied and rejecting otherwise.

$N$ accepts all inputs with a length greater than or equal to $m$. $N$also has$O\left(cm\right)$ states, indicating that it can work in polynomial time.

Because the clause is not satisfied if $N$accepts a, $N$is a nonsatisfying assignment .

As a result,N accepts all of's unsatisfactory assignments.

Let's say that minimising NFAs takes polynomial time. Construct an NFA that accepts unsatisfactory assignments. Also, if and only if is not satisfiable, N accepts any binary string.

In the case of new N' put the new minimization algorithm to the test. If $N\text{'}$ includes precisely one state and accepts all binary strings, reject $\varphi$ ; otherwise, accept $\varphi$ .

As a result, 3SAT has a polynomial time algorithm, and so P = NP.