Relaxed Random Search for Solving K-Satisfiability and its Information Theoretic Interpretation
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 11
Abstract
The problem of finding satisfying assignments for conjunctive normal formula with K literals in each clause, known as K-SAT, has attracted many attentions in the previous three decades. Since it is known as NP-Complete Problem, its effective solution (finding solution within polynomial time) would be of great interest due to its relation with the most well-known open problem in computer science (P=NP Conjecture). Different strategies have been developed to solve this problem but in all of them the complexity is preserved in NP class. In this paper, by considering the recent approach of applying statistical physic methods for analyzing the phase transition in the complexity of algorithms used for solving K-SAT, we try to compute the complexity of using randomized algorithm for finding the solution of K-SAT in more relaxed regions. It is shown how the probability of literal flipping process can change the complexity of algorithm substantially. An information theoretic interpretation of this reduction in time complexity will be argued.
Authors and Affiliations
Amirahmad Nayyeri, Gholamhossein Dastghaibyfard
Keywords
Related Articles
- EP ID EP241753
- DOI 10.14569/IJACSA.2017.081153
- Views 100
- Downloads 0
Model and Criteria for the Automated Refactoring of the UML Class Diagrams
Many papers have been written on the challenges of the software refactoring. The question is which refactorings can be applied on the modelling level. Based on the UML model, for example. With the aim of evaluating this...
Expensive Optimisation: A Metaheuristics Perspective
Stochastic, iterative search methods such as Evolutionary Algorithms (EAs) are proven to be efficient optimizers. However, they require evaluation of the candidate solutions which may be prohibitively expensive in many r...
A Defected Ground based Fractal Antenna for C and S Band Applications
In this paper, a modified ground based rectangular shaped fractal patch antenna will be presented. Since, the research community has witnessed a significant demand of both light weight and small sized micro-chip antenna...
A Conflict Resolution Strategy Selection Method (ConfRSSM) in Multi-Agent Systems
Selecting a suitable conflict resolution strategy when conflicts appear in multi-agent environments is a hard problem. There is a need to formulate a model for strategic decision making in selecting a strategy to resolve...
Implementation of Novel Medical Image Compression Using Artificial Intelligence
The medical image processing process is one of the most important areas of research in medical applications in digitized medical information. A medical images have a large sizes. Since the coming of digital medical infor...