I MERCOLEDì DEL DIMI

SEMINARIO

Describing the complexity of the “problem B is harder than problem A relation”

Paul Shafer

University of Leeds

Abstract
Some mathematical problems are harder than others. Using concepts from computability theory, we formalize the "problem B is harder than problem A" relation and analyze its complexity. Our results express that this "harder than" relation is, in a certain sense, as complicated as possible, even when restricted to several special classes of mathematical problems.