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 56
- Downloads 0
Fast Hybrid String Matching Algorithm based on the Quick-Skip and Tuned Boyer-Moore Algorithms
The string matching problem is considered as one of the most interesting research areas in the computer science field because it can be applied in many essential different applications such as intrusion detection, search...
IoT-Enabled Door Lock System
This paper covers the design of a prototype for IoT and GPS enabled door lock system. The aim of this research is to design a door lock system that does not need manual input from user for convenience purpose while also...
Comparative Analysis of K-Means and Fuzzy C-Means Algorithms
In the arena of software, data mining technology has been considered as useful means for identifying patterns and trends of large volume of data. This approach is basically used to extract the unknown pattern from the la...
An Enhanced Deep Learning Approach in Forecasting Banana Harvest Yields
This technical quest aspired to build deep multifaceted system proficient in forecasting banana harvest yields essential for extensive planning for a sustainable production in the agriculture sector. Recently, deep-learn...
Dynamic Service Adaptation Architecture
This paper proposes a software architecture for dynamical service adaptation. The services are constituted by reusable software components. The adaptation’s goal is to optimize the service function of their execution con...