### Duh!

You know something? Optimal simulation of storytelling is NP-hard for Grand Argument Stories.

Proof: A GAS can be encoded as an extended regex (a regular expression that includes backreferences to its own states previously in the processing). The GRAPH 3-COLORABILITY problem, which is known to be NP-hard, can be reduced to regex matching with backreferences. Thus, a GAS is equivalent to GRAPH 3-COLORABILITY in computational complexity: NP-hardness (at least).

Therefore, given some interactive storytelling system that refers to a GAS structure, finding compression algorithms that increase the system's storytelling

Okay then. At least I know what's up.

Proof: A GAS can be encoded as an extended regex (a regular expression that includes backreferences to its own states previously in the processing). The GRAPH 3-COLORABILITY problem, which is known to be NP-hard, can be reduced to regex matching with backreferences. Thus, a GAS is equivalent to GRAPH 3-COLORABILITY in computational complexity: NP-hardness (at least).

Therefore, given some interactive storytelling system that refers to a GAS structure, finding compression algorithms that increase the system's storytelling

*efficiency*- save some computational resources, particulary at runtime, by reusing objects - is possible, but none can be found that can compress the informational substrate, namely, the foundational Character Elements and their quad-wise interplay. Storytelling*effectiveness*- which I measure as "number of pleasant surprises per player per session" - can only ever be increased by human authors. Everything that's not reused - i.e., all "information" in the sense of (Algorithmic) Information Theory - needs to be thought-out and written before program execution, if the GAS structure is to be preserved during the interactionOkay then. At least I know what's up.

scheuring - 13. Jun, 11:23