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 103
- Downloads 0
Comparative Analysis of Online Rating Systems
Online rating systems serve as decision support tool for choosing the right transactions on the internet. Consumers usually rely on others’ experiences when do transaction on the internet, therefore their feedbacks are h...
Multi-Depots Vehicle Routing Problem with Simultaneous Delivery and Pickup and Inventory Restrictions: Formulation and Resolution
Reverse logistics can be defined as a set of practices and processes for managing returns from the consumer to the manufacturer, simultaneously with direct flow management. In this context, we have chosen to study an imp...
Big Brother: A Road Map for Building Ubiquitous Surveillance System in Nigeria
In this paper, we propose a method to improve the security challenges in Nigeria by embedding literally hundreds of invisible computers into the environment with each computer performing its tasks without requiring human...
A Portable Natural Language Interface to Arabic Ontologies
With the growing expansion of the semantic web and its applications, providing natural language interfaces (NLI) to end-users becomes essential to querying RDF stores and ontologies, using simple questions expressed in n...
Survey Paper for Software Project Team, Staffing, Scheduling and Budgeting Problem
Software project scheduling is a standout amongst the most imperative scheduling zones looked by Software project management team. Software development companies are under substantial strain to finish projects on time, w...