[texhax] using larger units to determine breaks?

[Toby Cubitt]

William Adams wrote:
> On May 6, 2009, at 8:06 AM, Morten Høgholm wrote:
> 
>> There is of course Michael Plass' thesis on the matter "Optimal
>> pagination techniques for automatic typesetting systems"
> 
> Gotta love the beginning of the last sentence of the abstract, ``For  
> certain simple badness functions, the pagination problem is NP- 
> complete...''
> 
> And for complex badness functions? What's more complex than  
> Nondetermininstic polynomial time?

PSPACE, EXP, and countless others. (OK, strictly speaking we don't know if
NP=PSPACE=EXP, so I'd be better off citing e.g. NEXP, since NEXP!=NP by
the time-hierarchy theorem).

Or maybe optimal pagination is undecidable :-)

Toby