Build all valid parenthesis in polynomial time

Question

Given some binary operator $\otimes : X\times X\to X,$ and list $x_1,\dots,x_n$ where $x_i\in X,$ can all possible expressions in $\otimes$ be computed within a number of operator applications polynomial in $n$?

We say an expression in an operator $\otimes$ and list $x_i$ is formed by placing $\otimes$ between all $x_i$ in order with some choice of parentheses. For example given the list $x,y,z,$ valid expressions are $(x\otimes y)\otimes z$ and $x\otimes (y\otimes z)$. Alternatively, an expression in $x$ is precisely $x$ and an expression in $x_1,\dots,x_n$ is an expression in $x_1,\dots,x_{k-1},x_k\otimes x_{k+1},x_{k+2},\dots,x_n$ for some $1\le k < n.$

We assume that there are no more than polynomially bounded amount of setting the parenthesis (because its given in the assignment) and thus it has to run in polynomial time.

---

I'm doubting my solution so far, here it goes:

We define two working sets

$ result = \{ \}$

$ vars = \{\}$

Every single input variable is a valid expressions if it is paired with another valid expression ( since our operand is two-valued), and we add them to the vars set.

Now iterate through lengths $ 2, \_,n$ and build all valid expressions like so:

For length $2$ we build all valid strings like so: $w_1 = (x_0 \circ x_1) , w_2 =(x_1 \circ x_2) \ldots $ and add them to the $vars$ set.

For length $>3$ we greedily iterate through the biggest available chunks in the $vars$ set and try to fill up the voids with items from our vars set until we reach length 3.

Once we reach length $n$ we add all generated expressions to the $res$ set and return.

One thing I'm stuck on right now is the complexity analysis, one iteration of the subexpression generation takes $n^2$ steps at most, when we reach length $n$ we get $n^3$ complexity (much like CYK, which is very similar to this algorithm).

---

But something feels fishy, I feel like I've made a mistake somewhere, can someone point me in the right direction ?

This is an assignment so full answers are discouraged, please give hints, once I get the grading of the answer I'll post it here for the afterworld to admire.

Answer 1

"We assume that there are no more than polynomially bounded amount of setting the parenthesis"

Your assumption is wrong. There are exponentially many such expressions. In particular, each such expression corresponds to a full binary tree with $n$ leaves (i.e., a binary tree where each non-leaf node has exactly 2 children). There are exponentially many such trees. Consequently, there are exponentially many such expressions.

It follows that you can't generate the list of all such expressions in polynomial time, since it takes exponential time even just to write down the answer (let alone to find it in the first place).