vincent@cs.toronto.edu (11/24/89)
Student Theory Meeting This week's theory meeting will be held in the Seminar Room (SF 3207) at 3pm, Friday. This week Pekka Orponen will give a talk on the structural complexity of problems. ABSTRACT We introduce a measure for the computational complexity of individual instances of a computational problem and study its properties. Intuitively, instances solved quickly by small special-case programs are easy, whereas instances whose solution in a given time limit requires a large program (or, trivially, table look-up) are hard. Formalizing this idea we obtain, among other things, natural characterizations of the class P and the class of P-immune sets. Further results include: the complexity of SAT instances grows at a logarithmic rate iff P = NP, and if EXPTIME \neq NEXPTIME, then SAT has infinitely many "hard" instances (i.e., ones that cannot be solved quickly essentially better than by table look-up).