Randomized algorithm approach for solving PCP
Journal Title: International Journal on Computer Science and Engineering - Year 2012, Vol 4, Issue 1
Abstract
Post Correspondence Problem is an undecidable problem that was introduced by Emil Post and is often used in proofs of undecidability. No efficient nondeterministic solution to the problem exists. The paper intends to present a nondeterministic solution to the above problem. The proposed work has been tested for some constrained inputs and the results were encouraging. The paper also discusses the application of genetic algorithms to the solution and the requisite analysis. The approach presents an Artificial Intelligence based solution to a problem which is used in theoretical computer science for proving purposes and can be extended to solve many non deterministic problems.
Authors and Affiliations
Harsh Bhasin , Nishant Gupta
Keywords
Related Articles
- EP ID EP129831
- DOI -
- Views 108
- Downloads 0
Two Factor Biometric Key for Secure Wireless Networks
The applications of wireless networks is steadily increasing through out the world. Wireless transactions are now appening in highly secure banking networks. To have more reliable networks, security of wireless networks...
Web Miner: A Tool for Discovery of Usage Patterns From Web Data
As there is a huge amount of data available online, the World Wide Web is a fertile area for data mining research. In recent years a various surveys have been performed on static data of web sites to perform web usage mi...
Performance Evaluation of L3 Handover Latency in MIPv6
Recent years in the field of mobile communications have brought two significant requirements – seamless service delivery and Quality of Service provisioning. Seamless mobility goes hand in hand with Mobile IPv6 protocol...
Preserving the Privacy and Sharing the Data using Classification on Perturbed Data
Data mining is a powerful tool which supports automatic extraction of unknown patterns from large amounts of data. The knowledge extracted by data mining process support a variety of domains like marketing, weather forec...
Optimization Technique for Maximization Problem in Evolutionary Programming of Genetic Algorithm in Data Mining
The optimization technique is used for the identification of some best values from the various populations. The Evolutionary algorithm is used as a basic concept of the Evolutionary Programming Strategy. To solve many of...