In this thesis we introduce the Resolution Machines as general model of computation in which each machine M consists of a finite number of general disjunctive clauses, and each problem instance x consists of a finite set of grounded disjunctive clauses. Moreover, the computation of M on input x is then executed using the resolution algorithm and variable substitution. The important part of this thesis is, Showing how to simulate a Turing machine with a resolution decider and if L is a decision problem that belongs in class P, when L is expressed with vocabulary = (X1,L1), there is a decider D = (ρ, τ, U, A) that decides L, and whose number of computation steps is bounded by a polynomial in the length of input x ∈ L. The Important findings of this thesis include: There is a resolution transducer that can encode an arbitrary instance C of 3SAT as a binary vector whose length is polynomial in the number of variables used by C and If P = NP, then there is a resolution decider D whose input vocabulary is the canonical CNF-SAT vocabulary and that can decide 3SAT in a polynomial number of inference steps.
|Commitee:||Lam, Shui, Moon, Ju Cheol|
|School:||California State University, Long Beach|
|Department:||Computer Engineering and Computer Science|
|School Location:||United States -- California|
|Source:||MAI 81/1(E), Masters Abstracts International|
|Subjects:||Computer science, Logic, Artificial intelligence|
|Keywords:||General model of computation, P vs NP, Resolution decider, Resolution machines, Resolution transducer, Satisfiability|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be