Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3044107.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Thresholds and Symmetries in Propositional Formulas
Author(s):Harris, Mitchell Alan
Doctoral Committee Chair(s):Dershowitz, Nachum
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
Abstract:Two problems with application to the analysis and design of algorithms concerning the satisfiability of propositional formulas are investigated. With respect to the first problem, there is great experimental evidence for a phenomenon known as the 'phase transition' of satisfiability, that is there is a sharp threshold, in the limit, between satisfiable and unsatisfiable formulas as the ratio of clauses to variables increases. To analyze this threshold, we count the number of satisfiable boolean formulas given in conjunctive normal form. The intention is to provide information about the relative frequency of boolean functions with respect to statements of a given size. This in turn will provide information about algorithms attempting to decide problems such as satisfiability and validity. First, we describe a correspondence between the syntax of propositions and the semantics of functions using a system of equations. Then we show how to solve such a system. This gives a general solution for any set of functions represented by atomic symbols acting as literals; we simplify the specific solution for the variables and their negations as literals. And finally we extract some asymptotics and threshold bounds from this solution. The second problem is the generation of distinct models of propositional formulas, when the variables can be permuted to form the same boolean function. A model is a complete assignment to the variables, but the permutations can render some of these assignments equivalent. Generation methods are developed for specific permutation groups.
Issue Date:2002
Type:Text
Language:English
Description:60 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2002.
URI:http://hdl.handle.net/2142/81600
Other Identifier(s):(MiAaPQ)AAI3044107
Date Available in IDEALS:2015-09-25
Date Deposited:2002


This item appears in the following Collection(s)

Item Statistics