Tossup

Two sets named for this term are equal if second-order logic is unaffected by the transitive closure operation on relations. In a proof about the permanent of a matrix, Leslie Valiant formulated a set named for this term prepended with a sharp sign. Inductively constructing sets denoted “capital pi-sub-i” and “capital sigma-sub-i” using oracles produces a “hierarchy” named for this term. This term appears twice in the name of a class identified with the set of Turing machines “with advice” that has a slash in its name. Reductions with runtime described by this term identify “complete” problems (10[1])such as SAT (“sat”). Whether a class named for this term is equal to its non-deterministic counterpart is the subject (10[1])of a Millennium Prize problem. (10[1])For 10 points, give this term that names the complexity class P. ■END■ (10[1]0[4])

Back to tossups

Buzzes

Summary