An Isaac Newton Institute Programme

Logic and Algorithms

Non-uniform hardness for NP via black-box adversaries

6th February 2006

Author: Atserias, A (Universitat Politecnica de Catalunya)

Abstract

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