Academic Journals Database
Disseminating quality controlled scientific knowledge

Randomized algorithm approach for solving PCP

Author(s): Harsh Bhasin | Nishant Gupta

Journal: International Journal on Computer Science and Engineering
ISSN 0975-3397

Volume: 4;
Issue: 1;
Start page: 106;
Date: 2012;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: Genetic Algorithms | NP Hard Problem | Artificial Intelligence | Post Correspondence Problem | Non Deterministic Problems.

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.
Affiliate Program     

Tango Jona
Tangokurs Rapperswil-Jona