Deciding the truth of a Quantified Boolean Formula (QBF) is a canonical PSPACE-complete problem. It provides a powerful framework for encoding problems that lie in PSPACE. These include many problems in automatic verification, and problems with discrete uncertainty or non-determinism. Two person adversarial games are another type of problem that are naturally encoded in QBF. It is standard practice to use Conjunctive Normal Form (CNF) when representing QBFs. Any propositional formula can be efficiently translated to CNF via the addition of new variables, and solvers can be implemented more efficiently due to the structural simplicity of CNF. However, the translation to CNF involves a loss of some structural information. This thesis shows that this structural information is important for efficient QBF solving, and shows how this structural information can be utilized to improve state-of-the-art QBF solving. First, a non-CNF circuit-based solver is presented. It makes use of information not present in CNF to improve its performance. We present techniques that allow it to exploit the duality between solutions and conflicts that is lost when working with CNF. This duality can also be utilized in the production of certificates, allowing both true and false formulas to have easy-to-verify certificates of the same form. Then, it is shown that most modern CNF-based solvers can benefit from the additional information derived from duality using only minor modifications. Furthermore, even partial duality information can be helpful. We show that for standard methods for conversion to CNF, some of the required information can be reconstructed from the CNF and greatly benefit the solver.

In the quest to understand cell behavior and cure genetic diseases such as cancer, the fundamental approach being taken is undergoing a gradual change. It is becoming more acceptable to view these diseases as an engineering problem, and systems engineering approaches are being deployed to tackle genetic diseases. In this light, we believe that logic synthesis techniques can play a very important role. Several techniques from the field of logic synthesis can be adapted to assist in the arguably huge effort of modeling cell behavior, inferring biological networks, and controlling genetic diseases. Genes interact with other genes in a Gene Regulatory Network (GRN) and can be modeled as a Boolean Network (BN) or equivalently as a Finite State Machine (FSM). As the expression of genes deter- mine cell behavior, important problems include (i) inferring the GRN from observed gene expression data from biological measurements, and (ii) using the inferred GRN to explain how genetic diseases occur and determine the ”best” therapy towards treatment of disease. We report results on the application of logic synthesis techniques that we have developed to address both these problems. In the first technique, we present Boolean Satisfiability (SAT) based approaches to infer the predictor (logical support) of each gene that regulates melanoma, using gene expression data from patients who are suffering from the disease. From the output of such a tool, biologists can construct targeted experiments to understand the logic functions that regulate a particular target gene. Our second technique builds upon the first, in which we use a logic synthesis technique; implemented using SAT, to determine gene regulating functions for predictors and gene expression data. This technique determines a BN (or family of BNs) to describe the GRN and is validated on a synthetic network and the p53 network. The first two techniques assume binary valued gene expression data. In the third technique, we utilize continuous (analog) expression data, and present an algorithm to infer and rank predictors using modified Zhegalkin polynomials. We demonstrate our method to rank predictors for genes in the mutated mammalian and melanoma networks. The final technique assumes that the GRN is known, and uses weighted partial Max-SAT (WPMS) towards cancer therapy. In this technique, the GRN is assumed to be known. Cancer is modeled using a stuck-at fault model, and ATPG techniques are used to characterize genes leading to cancer and select drugs to treat cancer. To steer the GRN state towards a desirable healthy state, the optimal selection of drugs is formulated using WPMS. Our techniques can be used to find a set of drugs with the least side-effects, and is demonstrated in the context of growth factor pathways for colon cancer.

In this thesis, we have considered two important problems, Boolean satisfiability (SAT) and derivative free optimization in the context of large scale quantum computers. In the first part, we survey well known classical techniques for solving satisfiability. We compute the approximate time it would take to solve SAT instances using quantum techniques and compare it with state-of-the heart classical heuristics employed annually in SAT competitions. In the second part of the thesis, we consider a few classically well known algorithms for derivative free optimization which are ubiquitously employed in engineering problems. We propose a quantum speedup to this classical algorithm by using techniques of the quantum minimum finding algorithm. In the third part of the thesis, we consider practical applications in the fields of bio-informatics, petroleum refineries and civil engineering which involve solving either satisfiability or derivative free optimization. We investigate if using known quantum techniques to speedup these algorithms directly translate to the benefit of industries which invest in technology to solve these problems. In the last section, we propose a few open problems which we feel are immediate hurdles, either from an algorithmic or architecture perspective to getting a convincing speedup for the practical problems considered.

Deciding the truth of a Quantified Boolean Formula (QBF) is a canonical PSPACE-complete problem. It provides a powerful framework for encoding problems that lie in PSPACE. These include many problems in automatic verification, and problems with discrete uncertainty or non-determinism. Two person adversarial games are another type of problem that are naturally encoded in QBF. It is standard practice to use Conjunctive Normal Form (CNF) when representing QBFs. Any propositional formula can be efficiently translated to CNF via the addition of new variables, and solvers can be implemented more efficiently due to the structural simplicity of CNF. However, the translation to CNF involves a loss of some structural information. This thesis shows that this structural information is important for efficient QBF solving, and shows how this structural information can be utilized to improve state-of-the-art QBF solving. First, a non-CNF circuit-based solver is presented. It makes use of information not present in CNF to improve its performance. We present techniques that allow it to exploit the duality between solutions and conflicts that is lost when working with CNF. This duality can also be utilized in the production of certificates, allowing both true and false formulas to have easy-to-verify certificates of the same form. Then, it is shown that most modern CNF-based solvers can benefit from the additional information derived from duality using only minor modifications. Furthermore, even partial duality information can be helpful. We show that for standard methods for conversion to CNF, some of the required information can be reconstructed from the CNF and greatly benefit the solver.

No description available.

Boolean Satisfiability (SAT) is a fundamental NP-complete problem of determining whether there exists an assignment of variables which makes a Boolean formula evaluate to True. SAT is a convenient representation for many naturally occurring optimization and decisions problems such as planning and circuit verification. SAT is most commonly solved by a form of backtracking search which systematically explores the space of possible variable assignments. We show that the order in which variable polarities are assigned can have a significant impact on the performance of backtracking algorithms. We present several ways of transforming SAT instances into non-linear objective functions and describe three value-ordering methods based on iterative optimization techniques. We implement and test these heuristics in the widely-recognized MiniSAT framework. The first approach determines polarities by applying Newton's Method to a sparse system of non-linear objective functions whose roots correspond to the satisfying assignments of the propositional formula. The second approach determines polarities by minimizing an objective function corresponding to the number of clauses conflicting with each assignment. The third approach determines preferred polarities by performing stochastic gradient descent on objective functions sampled from a family of continuous potentials. The heuristics are evaluated on a set of standard benchmarks including random, crafted and industrial problems. We compare our results to five existing heuristics, and show that MiniSAT equipped with our heuristics often outperforms state-of-the-art SAT solvers.

[Formulae and special characters can only be approximated here. Please see the pdf version of the Abstract for an accurate reproduction.] Artificial neural networks are universal function approximators that represent functions subsymbolically by weights, thresholds and network topology. Naturally, the representation remains the same regardless of the problem domain. Suppose a network is applied to a symbolic domain. It is difficult for a human to dynamically construct the symbolic function from the neural representation. It is also difficult to retrain networks on perturbed training vectors, to resume training with different training sets, to form a new neuron by combining trained neurons, and to reason with trained neurons. Even the original training set does not provide a symbolic representation of the function implemented by the trained network because the set may be incomplete or inconsistent, and the training phase may terminate with residual errors. The symbolic information in the network would be more useful if it is available in the language of the problem domain. Algorithms that translate the subsymbolic neural representation to a symbolic representation are called extraction algorithms. I argue that extraction algorithms that operate on single-output, layered feedforward networks are sufficient to analyse the class of multiple-output networks with arbitrary connections, including recurrent networks. The translucency dimensions of the ADT taxonomy for feedforward networks classifies extraction approaches as pedagogical, eclectic, or decompositional. Pedagogical and eclectic approaches typically use a symbolic learning algorithm that takes the network’s input-output behaviour as its raw data. Both approaches construct a set of input patterns and observe the network’s output for each pattern. Eclectic and pedagogical approaches construct the input patterns respectively with and without reference to the network’s internal information. These approaches are suitable for approximating the network’s function using a probably-approximately-correct (PAC) or similar framework, but they are unsuitable for constructing the network’s complete function. Decompositional approaches use internal information from a network more directly to produce the network’s function in symbolic form. Decompositional algorithms have two components. The first component is a core extraction algorithm that operates on a single neuron that is assumed to implement a symbolic function. The second component provides the superstructure for the first. It consists of a decomposition rule for producing such neurons and a recomposition rule for symbolically aggregating the extracted functions into the symbolic function of the network. This thesis makes contributions to both components for Boolean extraction. I introduce a relatively efficient core algorithm called WSX based on a novel Boolean form called BvF. The algorithm has a worst case complexity of O(2 to power of n divided by the square root of n) for a neuron with n inputs, but in all cases, its complexity can also be expressed as O(l) with an O(n) precalculation phase, where l is the length of the extracted expression in terms of the number of symbols it contains. I extend WSX for approximate extraction (AWSX) by introducing an interval about the neuron’s threshold. Assuming that the input patterns far from the threshold are more symbolically significant to the neuron than those near the threshold, ASWX ignores the neuron’s mappings for the symbolically input patterns, remapping them as convenient for efficiency. In experiments, this dramatically decreased extraction time while retaining most of the neuron’s mappings for the training set. Synthetic decomposition is this thesis’ contribution to the second component of decompositional extraction. Classical decomposition decomposes the network into its constituent neurons. By extracting symbolic functions from these neurons, classical decomposition assumes that the neurons implement symbolic functions, or that approximating the subsymbolic computation in the neurons with symbolic computation does not significantly affect the network’s symbolic function. I show experimentally that this assumption does not always hold. Instead of decomposing a network into its constituent neurons, synthetic decomposition uses constraints in the network that have the same functional form as neurons that implement Boolean functions; these neurons are called synthetic neurons. I present a starting point for constructing synthetic decompositional algorithms, and proceed to construct two such algorithms, each with a different strategy for decomposition and recomposition. One of the algorithms, ACX, works for networks with arbitrary monotonic transfer functions, so long as an inverse exists for the functions. It also has an elegant geometric interpretation that leads to meaningful approximations. I also show that ACX can be extended to layered networks with any number of layers.

Thesis (Ph.D.)--McMaster University (Canada), 1989. / Source: Dissertation Abstracts International, Volume: 62-13, Section: A, page: 0000.

Thesis (Ph. D.)--Carleton University, 2003. / Includes bibliographical references (p. 226-237). Also available in electronic format on the Internet.

Thesis (M. Phil.)--University of Hong Kong, 2009. / Includes bibliographical references (leaves 50-56) Also available in print.