Accession Number : ADA325899

Title :   An Algorithm for the Class of Pure Implicational Formulas,

Corporate Author : CINCINNATI UNIV OH

Personal Author(s) : Franco, John ; Goldsmith, Judy ; Schlipf, John ; Speckenmeyer, Ewald ; Swaminathan, R. P.

PDF Url : ADA325899

Report Date : 1996

Pagination or Media Count : 20

Abstract : Heusch introduced the notion of pure implicational formulas. He showed that the falsifiability problem for pure implicational formulas with k negations is solvable in time O(n exp(k)). Such falsifiability results are easily transformed to satisfiability results on CNF formulas. We show that the falsifiability problem for pure implicational formulas is solvable in time O((k exp(k))(n-sq)), which is polynomial for a fixed k. Thus this problem is fixed parameter tractable.

Descriptors :   *NONLINEAR PROGRAMMING, ALGORITHMS, PARAMETERS, POLYNOMIALS.

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE