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 90
- Downloads 0
Improving diffusion power of AES Rijndael with 8x8 MDS matrix
AES Rijndael is a block cipher developed by NIST as the Advanced Encryption Standard (AES) replacing DES and published as FIPS 197 in November 2001 [5] to address the threatened key size of Data Encryption Standard (DES)...
Classification of Herbs Plant Diseases via Hierarchical Dynamic Artificial Neural Network after Image Removal using Kernel Regression Framework
When herbs plants has disease, they can display a range of symptoms such as colored spots, or streaks that can occur on the leaves, stems, and seeds of the plant. These visual symptoms continuously change their color, sh...
A review on various methods of image thresholding
Recent years have witnessed the rapid growth of degraded images due to the increasing power of Computing and the fast development of Internet. Because of this tremendous increase of quality of degraded images, there is a...
COLLABORATIVE ANOMALY-BASED INTRUSION DETECTION IN MOBILE AD HOC NETWORKS
Intrusion Prevention is first line of defense against attacks in MANET. Intrusion Detection and response presents a second line of defense. New vulnerabilities will continue to invent new attack methods so new technology...
Recent Advances in SRE Research
The importance and the real potential of the Requirements ngineering is now being well recognized. A series of reversed as well as assorted researches are underway particularly on ‘ways to incorporate security right fro...