Word Problem over Finite Groupoids

Question

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://www.algorist.com/algowiki/index.php/Divide-TADM2E#8-22

The problem asks you to write a polynomial-time algorithm using DP which solves a special case of the Word Problem over finite groupoids:

Given a finite groupoid $G$, a word $s$ on $G$ and an $x \in G$, find out whether it is possible to parenthesize $s$, such that its evaluation will yield $x$. Example from the book:

\begin{array}{c|ccc} & a & b & c \\ \hline a & a & c & c \\ b & a & a & b \\ c & c & c & c \\ \end{array}

For instance, consider the above multiplication table and the string $bbbba$. Parenthesizing it $(b(bb))(ba)$ gives $a$, but $((((bb)b)b)a$ gives $c$.

So far I managed to write a naive $O(n!)$ recursive algorithm in Python:

def i(x):
    return ord(x) - ord('a')

def mul(x, y):
    return groupoid[i(x)][i(y)]

# rewrite('abc', 1) = 'ac'
# rewrite('abc', 0) = 'cc'
def rewrite(word, i):
    return word[:i] + mul(word[i], word[i+1]) + word[i+2:]

def search(word, x):
    exists = (word == x)
    for i in range(0, len(word) - 1):
        if exists:
            break
        exists |= search(rewrite(word, i), x)
    return exists

word = sys.argv[1]
x = sys.argv[2]
exists = search(word, x)
print('Solution exists' if exists else 'Unsolvable')

Although we can memoize search, it won't give us polynomial time, since memoization space is of a factorial order. This is where I'm stuck.

The problem here is to somehow reduce the factorial search-space of all possible reductions from $s$ on $G$ to a polynomial search-space, which will depend only on $|s|$ and $|G|$. Can you please help me with that? Any other hints?

Answer 1

This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill?

In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The subproblems should be refined enough so that we can solve the larger subproblems from the solutions of the smaller subproblems. Please take a moment to appreciate how the subproblems are defined below.

Compute $dp[i][j]$, the set of all possible values of $x_{i}x_{i+1}\cdots x_j$, where $1\le i\le j\le n$.

The goal element $a$ is a possible value of $x$ if and only if $dp[0][n]$ contains $a$.

How to compute $dp[i][j]$?

The base case, $dp[i][i]$ is the set of a single element, $x_i$.

How about the case when $j\ge i+1$? Note a parenthesization of $x_ix_{i+1}\cdots x_j$ means to parenthesize it into two parts, $(x_i\cdots x_t)(x_{t+1}\cdots x_j)$ for some $i\le t\lt j$, followed by a parenthesization of the front part $x_i\cdots x_t$ and a parenthesization of the behind part, $x_{t+1}\cdots x_j$. So $dp[i][j]$ contains all products of the form $f\cdot b$, where $f$ is a possible value of the front part and $b$ is a possible of the behind part. Note both the front part and behind part are shorter than the whole, $x_ix_{i+1}\cdots x_j$.

In other word, in order to compute $dp[i][j]$, we can iterate $f$ through all elements in $dp[i][t]$ and $b$ through all elements in $dp[t+1][j]$, adding the product $f\cdot b$ to $dp[i][j]$.

There are $n(n-1)/2$ choices for $i$ and $j$. There are at most $n$ choices for $t$. There are at most $k$ choices for $f$. There are at most $k$ choices for $b$. Depending on the implementation, it takes $O(k\cdot k\cdot k)$ or much less time to compute product $f\cdot b$ and add it to a set of at most $k$ elements. Hence the time-complexity of the algorithm is polynomial in $n$ and $k$.