Dissertation > Excellent graduate degree dissertation topics show

The Bounds of Critical Function for (k,s)-SAT

Author: GongPing
Tutor: XuDaoYun
School: Guizhou University
Course: Basic mathematics
Keywords: SAT (k,s)-CNF Minimal unsatisfiable formula The probabilistic method Randomize algorithm
CLC: O141
Type: Master's thesis
Year: 2006
Downloads: 23
Quote: 0
Read: Download Dissertation

Abstract


(k, s)-SAT is the propositional satisfiable problem restricted to instances where each clause has exactly k distinct literals and every variable occurs at most s times. It is known that there exists an exponential function f such that for s ≤ f{k), all （k, s）-SAT instances are satisfiable, but （k, f（k）+1）-SAT is already NP-complete（k> 3）. We term f（.） critical function. Exact values of f are only known for k = 3 and k = 4, and it’s open whether f is computable. Thus, to study the bounds of f（k） is of theoretical research senses. The best known lower and upper bounds on f（k） are Ω（2k/k） and O（2k/kα）, where α = log34 -1 ≈ 0.26, respectively.In [SS], S. Hoory and S. Sezider obtain a computable upper bound function for f{k)（k ≥ 3）. The approach is to create some instance in （k,s）SAT by calculating stairways, which correspond to constructing some desired minimal unsatisfiable formulas with deficiency one. However, the calculation for stairways is nondeter-ministic. It is difficult to determine the upper bounds of f（k） for k.In this thesis, we have following contributions:（1） A tree rule is introduced to reduce the steps of calculating stairways, and a deterministic calculation for stairways is presented to get the upper bounds for f（k）（k ≥ 3）. The deterministic algorithm is practical, and the upper bounds are near the bounds S. Hoory and S. Sezider got.（2） A randomize algorithm for outputting a true assignment for a given formula is presented. Based on it and by probabilistic method, we prove that, for every integer k ≥ 2, each formula F in （k, *） - CNF with less than 0.58 2k is satisfiable. In addition, by the Lovasz Local lemma, we get a new lower bound of f（k）, Ω （2k/k）, which improves the result Ω（2k/k）..

Related Dissertations

  1. The Fractional Chromtic Numbers of Some Graphs,O157.5
  2. Modern Urban Public Recreational Space Seat Design,TS664.01
  3. Decision Analysis and Implementation of the Tax System Human Resources,TP311.52
  4. GSM / GPRS wireless data communications terminal technology,TN929.53
  5. Research on the Automatic Test Pattern Generation for the Digital Integrated Circuits,TN431.2
  6. Research on Formal Methods in Arithmetic Circuit Verification,TP332.2
  7. Study on Algorithms of Test Pattern Generation for Sequential Circuits,TN706
  8. Research on Faulty Test Pattern Generation Methods for Digital Circuits,TN792
  9. Equivalence Checking and Test Generation Using Boolean Satisfiability,TN791
  10. Research on RTL-gate Equivalence Checking,TN47
  11. Research on the Upper Bounds and the Phase Transformation of the Automated Reasoning and the Planning,TP18
  12. Automated Loop Invariant Generation for Program Verification,TP311.11
  13. Development of Magnetic Bistable MEMS Electromagnetic Microrelay,TM581.3
  14. Study on Social Cognitive Optimization’s Improvements and Its Application,TP391.9
  15. Linear formula to meet the complexity of the decision problem,TP301.5
  16. Can -CNF satisfiability algorithm to simplify,TP301.6
  17. Research on Test Pattern Generation of Asynchronous Circuit,TN79
  18. Research on Model Construction Technology of Virtual Mining in Digital Open-pit and Its Application,TD804
  19. The Study of Pseudo-Boolean Satisfiability Algorithm and Its Application in FPGA Routing,TN791
  20. Thought on the Administrative Law Enforcement Responsibility System of the Basic SAT Institution,F812.42

CLC: > Mathematical sciences and chemical > Mathematics > Mathematical logic,mathematical foundations > Mathematical logic ( symbolic logic )
© 2012 www.DissertationTopic.Net  Mobile