[texhax] using larger units to determine breaks?
tsc25 at cantab.net
Wed May 6 14:34:26 CEST 2009
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-
> 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 :-)
More information about the texhax