Romani, Shadab (2016) Succinct representations of Boolean functions and the Circuit-SAT problem. Masters thesis, Memorial University of Newfoundland.
- 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.
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)|
|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|
|Library of Congress Subject Heading:||Computable functions; Computational complexity; Turing machines; Algebra, Boolean|
Actions (login required)