Time bounds on the parallel evaluation of arithmetic expressions. Solving a problem in eigenvalue approximation with a symbolic algebra system. Bounds for multiprocessor scheduling with resource constraints. The computation of powers of symbolic polynomials. Computational algorithms for the enumeration of group invariant partitions.
Every prime has a succinct certificate.
Finding a maximum cut of a planar graph in polynomial time. Complete register allocation problems. Ashok K. Chandra and C. K. Wong . Worst-case analysis of a placement algorithm related to storage allocation. Arnold L. Rosenberg .