Succinct representations of Boolean functions and the Circuit-SAT problem

Romani, Shadab (2016) Succinct representations of Boolean functions and the Circuit-SAT problem. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (304kB)

Abstract

We study the question whether there is a computational advantage in deciding properties of Boolean functions given a succinct description of the function (such as a Boolean circuit) as opposed to black-box access to the function. We argue that a significant computational advantage for a large class of properties implies a non-trivial algorithm for the Circuit Satisfiability (Circuit-SAT) problem. In particular, we show that if there is a property with strong black-box lower bounds yet decidable in BPP, which also has a highly sensitive instance computable by a small circuit, then there is a non-uniform sub-exponential algorithm for the Circuit-SAT problem. Additionally, we analyze variants of this question for other computational models.

Actions (login required)

View Item