skip to content

Non-uniform hardness for NP via black-box adversaries

Presented by: 
A Atserias [Politecnica de Catalunya]
Monday 6th February 2006 - 11:00 to 12:00
INI Seminar Room 1

We may believe SAT does not have small Boolean circuits. But is it possible that some language with small circuits looks indistiguishable from SAT to every polynomial-time bounded adversary? We rule out this possibility. More precisely, assuming SAT does not have small circuits, we show that for every language $A$ with small circuits, there exists a probabilistic polynomial-time algorithm that makes black-box queries to $A$, and produces, for a given input length, a Boolean formula on which $A$ differs from SAT. This will be a blackboard lecture (no slides).

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons