2
$\begingroup$

Wikipedia defines straight-line programs in the following manner:

In mathematics, more specifically in computational algebra[disambiguation needed], a straight-line program (SLP) for a finite group G = 〈S〉 is a finite sequence L of elements of G such that every element of L that belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.

This is a fairly confusing definition to unpack. However, in some meaningful sense, I believe the main idea here is that there are no comparisons allowed. Since there are no comparisons, the "computation tree" ends up being a straight line - hence the name "straight-line program."

In modern terms, is this the correct idea? Or are there even more subtle restrictions than this on what sorts of programs are allowed to be straight-line programs?

$\endgroup$
2
$\begingroup$

A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations.

A straight-line program for a finite group $G$ is a straight-line program in a very simple language with an unlimited number of registers $r_1,r_2,r_3,\dots$ and with only two legal operations:

  • $r_i := \text{inverse}(r_j)$

  • $r_i := \text{multiply}(r_j,r_k)$

You specify $i,j,k$ for each line of the program; those are constants. Each register holds a group element.


For instance, the following is a straight-line program that computes the cube of the element in $r_1$ and stores the result in $r_3$:

  • $r_2 := \text{multiply}(r_1, r_1)$
  • $r_3 := \text{multiply}(r_1, r_2)$

Here is another program that computes the same thing, but in a different way:

  • $r_2 := \text{multiply}(r_1, r_1)$
  • $r_4 := \text{multiply}(r_2, r_2)$
  • $r_5 := \text{inverse}(r_1)$
  • $r_3 := \text{multiply}(r_4, r_5)$
$\endgroup$
  • $\begingroup$ Thanks, makes sense. So for some RAM with whatever instruction set, an algorithm for on that RAM is an SLP iff it halts and has no comparisons/branching. Right? $\endgroup$ – Mike Battaglia Jun 2 '17 at 23:55
  • $\begingroup$ @MikeBattaglia, no. These programs (SLPs for groups) have only registers -- no memory, no pointers, no arrays, no indirect addressing, etc. $\endgroup$ – D.W. Jun 2 '17 at 23:56
  • $\begingroup$ How are you distinguishing between "registers" and "memory" here? For most RAM models I've studied, the only "memory" I've seen is the set of registers. But if the additional restriction here is that indirection is also not allowed, that makes sense. $\endgroup$ – Mike Battaglia Jun 3 '17 at 0:05
  • $\begingroup$ @MikeBattaglia, memory lets you do something like $r_2 = \text{load}(r_1)$, i.e., read from an address specified by the value in register $r_1$. This model doesn't let you do that. All register indices must be compile-time constants -- you can't have something like $r_{r_2}$. In other words, no array lookups, no table lookups, no pointers, no indirection. $\endgroup$ – D.W. Jun 3 '17 at 3:05
  • $\begingroup$ Thanks, that is interesting. I'm wondering, what is the central idea behind these restrictions? I guess the idea is that you can effectively "simulate" a comparison with indirection, so if you're banning the former you might as well ban the latter, right? $\endgroup$ – Mike Battaglia Jun 5 '17 at 16:47

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.