Some results on evaluating and checking functions for software redundancy (prolog, nondeterministic transducer, complexity)
Louise Guthrie · 1985
This thesis studies the time complexity of verification and computation of functions in order to answer two questions motivated by the research of Adams and Smartt on software reliability. The question of when a Prolog program can check a result in less time than it takes to compute that result was asked by Smartt because it has implications for implementing a language designed for software redundancy. The notion of length complexity of a logic program defined by Shapiro is extended to define a complexity measure for Prolog. Using this measure of complexity, it is shown that the time complexity of verifying a result using a given Prolog program P is never greater than the time to compute that result using P. A class of Prolog programs for which the time to verify a result is the same as the time to compute that result is identified. A characterization is given, in the class of functions whose output size is bounded by a polynomial of the input size, of those functions which can be checked in polynomial time. This characterization is obtained by defining a reducibility between partial multivalued functions called graph reducibility, and showing that the graph of such a function is in P if and only if the function is graph reducible to the search function for satisfiability. For single-valued functions, graph reducibility is shown to be stronger than the two reducibilities defined by Capka for single-valued functions. A function which is graph-complete for the class NPMU of Book, Long and Selman is exhibited, and it is shown that the existence of a graph-complete function for their class NPSU is equivalent to P = NP. Finally, the subclass of NPMU in which membership in the graph of the function can be decided in polynomial time (NPMUPG) is shown to be a proper subclass of NPMU if and only if P (NOT=) NP.