Auto and self-reducibilities within NP

Piotr Faliszewski
Department of Computer Science
University of Rochester
pfali@cs.rochester.edu

ABSTRACT

In real life we often do not want to ask certain questions directly. For example, instead of asking a child for its age we can ask which grade he or she attends. Then, based on this information, we can easily calculate how old the child is. It turns out that this ability to rephrase questions also shows up in computational complexity theory---for many problems instead of asking a yes/no question about some entity x we can ask a couple of yes/no questions about some other entities, and deduce the answer that we were originally seeking.

In this talk I will discuss the issue of rephrasing questions with respect to one of the most important complexity classes, NP. Technically speaking, I will present the notions of self- and autoreducibility that catch the property of rephrasing. I will concentrate on the issue of all NP-complete sets being either self- and autoreducible. I will present a result showing that NP behaves differently with respect to these notions.

Colloquia Series page.