0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I don't understand your question. I don't understand what set of strings you're trying to generate -- in particular, aren't there infinitely many of them? $x!$, $x!!$, $x!!!$, ... $\endgroup$ – David Richerby Jun 6 '18 at 16:22
  • 3
    $\begingroup$ Given that there are exponentially many expressions using only one binary operator, I'm not sure what you mean by polynomial time. If you mean time polynomial in the output length, then this is indeed possible, using a simple recursive approach (with the caveat that unary operators are troublesome). $\endgroup$ – Yuval Filmus Jun 6 '18 at 17:32
  • $\begingroup$ I've edited the post, I hope its more more understandable now, to put it more bluntly I'm looking for all possible valid ways to set the parenthesis when dealing with a two valued operand. $\endgroup$ – zython Jun 6 '18 at 19:58
  • $\begingroup$ I don't understand your algorithm. I don't understand what "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" means concretely. I don't think that's specific enough that I would know what you are proposing the algorithm should do in that step. I suggest thinking about how to write pseudocode to do that step. $\endgroup$ – D.W. Jun 7 '18 at 0:11
  • $\begingroup$ For example, I don't know what a "chunk" is (is it the same as an expression?), or what a "void" is, or what it means to "fill up the voids" -- and "try to fill up the voids" doesn't tell me how you plan to do that. I don't know what you mean by "greedily iterate" or how that differs from "iterate". I don't know what makes a chunk available or unavailable. And so on. $\endgroup$ – D.W. Jun 7 '18 at 0:11
2
$\begingroup$

"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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.