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.

[img] [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 (297Kb)

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.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/12159
Item ID: 12159
Additional Information: Includes bibliographical references (pages 44-47).
Keywords: Boolean Circuits, Circuit Satisfiability, Rice's Theorem, Complexity Theory
Department(s): Science, Faculty of > Computer Science
Date: April 2016
Date Type: Submission
Library of Congress Subject Heading: Computable functions; Computational complexity; Turing machines; Algebra, Boolean

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics