##
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.