# What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n [closed]

Note that this is not duplicate of my previous question: how to simplify algebraic expressions, though it is similar, but still this is different, this is not the same.

I need an algorithm that either proves or refutes that:

∀X,Y,Z,n,i,j,k,l: X∈{A,B} ∧ Y∈{A,B} ∧ Z∈{A,B} ∧ i,j,k,l≥0 ∧ n≥1 ∧ i+j+k+l≤n-3

$\Sigma$ (A+B)iX(A+B)jY(A+B)kZ(A+B)l = (A+B)n

Note that Σ here stands for sum with the operator +, which is union of set of words.

It should be noted that i,j,k and l are changing from term to term, keeping that:

i≥0 ∧ j≥0 ∧ k≥0 ∧ l≥0 ∧ i+j+k+l≤n-3

The only one that is not changing in the sum is n.

The algebraic rules are:

The operator + in this algebra is binary idempotent as I read about the semiring on wikipedia that someone linked me in the comments.

∀n,e1, ... , en ∈ {A,B,(A+B)}

e1...en+e1...en=e1...en

Where e1...en is concatenation of all e1 to en

In other words, sum of same expressions is equal to same expression, e.g. A+A=A, B+B=B, (A+B)+(A+B)=(A+B), AB+AB=AB, BA+BA=BA, A2+A2=A2, B2+B2=B2, (A+B)2+(A+B)2=(A+B)2 and etc, like in regular expressions.

That's because, each expression is a set of words, and the operator + is suppose to be union of the sets.

AA=A2, BB=B2, (A+B)(A+B)=(A+B)2, AAA=A3, BBB=B3, (A+B)(A+B)(A+B)=(A+B)3, ... , AAB=A2B, ABB=AB2

Note that ABA≠A2B

The power of A means how many times A appears in row, and the power of B means how many times B appears in row, and the power of (A+B) means how many (A+B) appears in row.

A(A+B) = AA+AB=A2+AB

B(A+B) = BA+BB=BA+B2

(A+B)A = AA+BA = A2+BA

(A+B)B = AB+BB = AB+B2

Thus:

A(A+B)B = (AA+AB)B = (A2+AB)B = A2B+ABB = A2B+AB2

Unlike in regular expressions, in this algebra you can do the following:

AB+BA=2AB

2AB says that in the set there are exactly 2 different words that contains 1 letter 'A' and 1 letter 'B' in the set.

Thus: 2BA=2AB, 2BA means the same thing as 2AB means.

3AB=2AB, because 3AB says that in the set there are exactly 3 different words that contains 1 letter 'A' and 1 letter 'B' in the set, but this is impossible combinatorially.

In general, the coefficient is natural number that says how many words exist in the set, when you specify how many As and Bs are contained in each word in the set.

If the coefficient is larger than the number of possible different words combinatorially, the expression is equals to the same expression, but with smaller coefficient that is equals to the number of possible different words combinatorially.

Thus 3BA=2BA, because only 2 words with 1 letter A and 1 letter B is possible, but not 3.

It should be noted that when the coefficient is smaller than the number of possible words combinatorially, the set is undefined, i.e. for example:

2A2B says that in the set there are 2 words that each contains 2 letters A and 1 letter B, but combinatorially there exists 3 different words.

So:

Does 2A2B={AAB,ABA} ? Does 2A2B={ABA,BAA} ? Does 2A2B={AAB,BAA} ?

This is unknown! It's known that it can be equals to either of these sets, but it's unknown which exactly.

But sure that 2A2B≠{AAA,BBB}!

The algorithm should be careful! Because that union is commutative operator thus the plus operator marked as +, i.e. changing the order does not change the result.

∴ A+B=B+A

AB+BA=BA+AB

Note that: AB≠BA

Because concatenation isn't commutative operator, unless the coefficient is larger than 1.

But:

1. AB+AB+BA=AB+BA+AB ∵ AB+BA=BA+AB

But:

1. AB+AB+BA = AB+BA = 2AB ∵ AB+AB=AB

and

1. AB+BA+AB = 2AB+AB = 3AB

∴ 2AB=3AB ∵ 1, 2 and 3

In this case it works, because really 3AB=2AB and this already explained above by the definition of coefficient of a word

But in the following case, it doesn't work:

1. AAB+AAB+BAA = AAB+BAA+AAB ∵ AAB+BAA = BAA+AAB

2. AAB+AAB+BAA = AAB+BAA = 2AAB ∵ AAB+AAB=AAB

3. AAB+BAA+AAB = 2AAB+AAB = 3AAB

∴ 2AAB=3AAB ∵ 4, 5 and 6

But this is fallacy ∵ 2AAB≠3AAB ∵ |2AAB|≠|3AAB|

∵ |2AAB|=2 ∧ |3AAB|=3 ∧ 2≠3 according to the definition of coefficient of a word.

Where || is the operator that returns the cardinality of the set, and because that all sets are finite in this math, it returns the number of words in the set.

Even though it cannot be determined what exactly is 2AAB, still it can be determined that |2AAB|=2, but note that |4AAB|=3, not 4, because 4AAB=3AAB and |3AAB|=3, because there is no 4 different words that contains 2 letters 'A' and 1 letter 'B'.

As you can see the result can be wrong and incorrect due to fallacy and to avoid this, the algorithm must first in every iteration to scan the entire string and detect same expressions and eliminate them. Then to sum up the others.

In this case, when the following expression is given:

AAB+BAA+AAB

The algorithm should notice that AAB repeats itself and eliminate all the repeatings, until there is only 1 occurrence.

After first scan:

AAB+BAA+AAB

Now eliminate AAB so the string becomes:

AAB+BAA

Then:

2AAB

And this is the correct result.

It should be noted that in this algebra, you can also use the binomial theorem.

For instance:

(A+B)2=A2+2AB+B2

And this is correct, because (A+B)2 is the set of all words that has length of 2, where the alphabet is {A,B}.

The other side is union of 3 sets, where A2={AA}, B2={BB} and 2AB={AB,BA}, so A2+2AB+B2={AA}∪{AB,BA}∪{BB}=(A+B)2

It seems that this works with power of 2, but this should work with any other power, not only 2, thus the binomial theorem applies, because for any natural number n, (A+B)n is the set of all words of length n, where the alphabet is {A,B}. Check it out! According to the definition of coefficient of a word, the binomial theorem works!

Note that kleene star is undefined in this algebra, unlike in regular expressions, i.e. the operator * does not exist in this algebra.

The purpose of brackets () in this algebra is to write the union of two expressions shorter, if both expressions have identical prefixes or/and identical infixes or/and identical suffixes.

That's all the rules.

I don't expect for quick answers, I will wait.

I do understand that you need the time to read my question over and over again until you understand everything or you have questions to ask.

I have already said what is given to the algorithm in the beginning of this question.

The algorithm suppose to return true, if the given expression is equals to (A+B)n or false otherwise for any given natural number n.

To determine if the given expression does equal to (A+B)n, the algorithm will have to simplify the given expression, but only by applying all the rules I have talking about above.

It should be easy to write the pseudo code of this algorithm to do this task, but I want to know what would be both the time and space complexity of this algorithm.

I think it should be polynomial both in time and space, but I need a proof.

EDIT: Someone noted that I asked 3 questions, but I thought that I asked only 1 question.

My real question is: what is the complexity of this problem?

Although if there exists polynomial algorithm that solves this problem, then by definition of the complexity class P, this problem suppose to be in P, so giving polynomial algorithm as an answer to the question: "What is the algorithm that solves this problem?", also answers that question: "What is the complexity of this problem?", because this answer implies that this problem is in P.

If the answer also answers indirectly the question "What is the complexity of this problem?" then it also answers indirectly the question "What is the complexity of this algorithm?", because if I inferred from the answer that the problem is in P, then the algorithm in the answer must be polynomial in time and space.

That's the reason that for me, these 3 questions are 1 question, because 1 answer can answer all these 3 questions, 1 of them directly, the 2 others indirectly.

I also admit that this question is very long, that's why I already said that I don't expect for quick answers.

I can wait for answer even until the next week.

I am not rushing or something.

I know that you need the time to understand this algebra.

I also apologize for my bad formatting.

Please let me know what is bad in the format of my question and I will improve my question.

In the mean time, I am going to try to answer my question by myself, but this will take some time.

I don't think that this question is easy.

• Ugh, this is long. I can't tell: is this a computability, complexity, or algorithm analysis question? That motley mix of tags needs to be cleared out! – Raphael Jul 13 '17 at 18:08
• I have no time to read your very long and badly formatted (we have MathJax!) question (especially since you don't seem to know what exactly it's about!) so you'll have to decide on how to proceed.. – Raphael Jul 13 '17 at 18:44
• Sorry, but this is far too long to read. When you start by expressing the thing you're looking for as a multi-line first-order formula, nobody is going to read any further. – David Richerby Jul 13 '17 at 20:04
• You want to prove something that involves a sum. What is the sum taken over? I can't see any free variables; it looks like the term inside the sum is a constant (all variables are instantiated by the outermost quantifiers). – D.W. Jul 13 '17 at 20:11
• I gave you a link to a tutorial on MathJax. As I mentioned previously, I don't recommend changing the text size -- that's rarely a good idea. If you want more help with MathJax, you can use search and you'll probably find lots of documentation. – D.W. Jul 13 '17 at 21:47

You don't need an algorithm; you just want to prove a theorem. This isn't a question about computer science algorithms, so much as a question about mathematics. The theorem is tedious but not difficult to prove.

I suggest you start by practicing proving some simpler statements. For instance, in your algebra,

$$(A+B)^i (A+B)^{n-i} = (A+B)^n$$

is true for all $i,n$ with $0 \le i\le n$. This can be proven by simply considering all cases; you consider any term in the right-hand side, and prove that it is in the left-hand side, and vice versa. The right-hand side is a sum of terms, where each term is a sequence of $n$ letters. Each such term appears on the left-hand side, too.

Similarly, you can prove

$$\sum_{i=0}^n (A+B)^i (A+B)^{n-i} = (A+B)^n$$

is true in your algebra for all $n$. In particular, using the above fact, we see that

$$\sum_{i=0}^n (A+B)^i (A+B)^{n-i} = \sum_{i=0}^n (A+B)^n = (A+B)^n.$$

It's also true that

$$\sum_{i=0}^n \sum_{X\in \{A,B\}} (A+B)^i X (A+B)^{n-1-i} = (A+B)^n.$$

A helpful step in that derivation is that

\begin{align*} \sum_{X\in \{A,B\}} (A+B)^i X (A+B)^{n-1-i} &= (A+B)^i \left(\sum_{X\in \{A,B\}} X \right) (A+B)^{n-1-i}\\ &= (A+B)^i (A+B) (A+B)^{n-1-i}\\ &= (A+B)^i (A+B)^{n-i}. \end{align*}

To help you learn how to do proofs like this, I suggest that you write a proof for each of these statements.

Once you understand those methods, you should be able to prove that your statement holds. It's just a more complicated version of these examples.

• Actually I want to write a GUI (graphics user interface) application that does this proof (maybe windows or website uses javascript or flash), so I do need the algorithm after all, but the complexity of this algorithm must be polynomial both in time and space, because I don't want that my application will encounter out of memory or stack overflow or the user will have to wait some thousands of years until the application has finished the proof for some very long and large input. Sorry that I didn't say this in my question before. You answer is good. At least it gives me a direction about how – Farewell Stack Exchange Jul 13 '17 at 22:05
• to implement my application. Thanks you. – Farewell Stack Exchange Jul 13 '17 at 22:07
• Since you only have one theorem to prove, you can prove it yourself with pencil and paper, and then hardcode the proof into the program and have it just print it out. You don't need an algorithm when there is only one problem instance that will ever be solved. I don't see what a GUI has to do with it. – D.W. Jul 14 '17 at 5:40
• The purpose of the GUI is to let the user to input an expression and the application will output on the screen or window or browser the steps that the algorithm did in the proof until it arrives at (A+B)^n for any natural number n, or not. – Farewell Stack Exchange Jul 14 '17 at 11:08