What is the complexity to show this theorem?

Question

Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1).

There is need to show that the sum of all regular expressions is either equal to or not equal to the regular expression, which is n-1 concatenations of (0+1).

I want to know what is the complexity to show this theorem?

Actually it is possible to open up all brackets and parentheses, but this increases number of regular expressions in the sum to some exponential number.

Proof in this way is very long and requires a lot of large papers.

I want to know if there is more easier, efficient and faster way to do this proof?

Answer 1

This is just SAT in disguise. Given a clause, you can encode the set of assignments falsifying the clause as a sum of the type you indicated. The formula is unsatisfiable iff every assignment falsifies some clause, that is, iff the sum of the regular expressions is $(0+1)^{n-1}$.