Events — Colloquia & Seminars
Hierarchies of Complexity Classes
Speaker: Stathis Zachos,
Date: Friday, September 7, 2007
Talk: 5:00 PM, 366 WVH
Abstract
Computational Complexity deals with the classification of problems into classes of hardness, called complexity classes. Complexity classes are defined by modifying structural parameters, such as the model of computation (Turing Machine, RAM, Finite Automaton, PDA, LBA, PRAM, Monotone Circuits), the mode of computation (deterministic, nondeterministic, probabilistic, alternating, uniform parallel), the kind of the automaton (Decider, Acceptor, Generator, Transducer, Counting), the resources (time, space, # of processors, circuit size and depth) and others: randomness, oracles, interactivity, promise, advice, operators. Some of the most important questions concern inclusion and separation relations among complexity classes. This line of research has led to numerous definitions of complexity classes, as well as inclusion sequences of classes known as "complexity hierarchies". We will review some of the most interesting ones, including the Polynomial-Time Hierarchy, a Counting Hierarchy and an Approximability Hierarchy.
Brief Biography
none provided