Dissertation/Thesis Abstract

Resolution Machines
by Sagwal, Himanshu, M.S., California State University, Long Beach, 2019, 53; 13857510
Abstract (Summary)

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 xL. 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.

Indexing (document details)
Advisor: Ebert, Todd
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
Source Type: DISSERTATION
Subjects: Computer science, Logic, Artificial intelligence
Keywords: General model of computation, P vs NP, Resolution decider, Resolution machines, Resolution transducer, Satisfiability
Publication Number: 13857510
ISBN: 9781085559775
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest