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
DOWNLOAD PDF 
Original page
Keywords: Genetic Algorithms | NP Hard Problem | Artificial Intelligence | Post Correspondence Problem | Non Deterministic Problems.
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.
Journal: International Journal on Computer Science and Engineering
ISSN 0975-3397
Volume: 4;
Issue: 1;
Start page: 106;
Date: 2012;
VIEW PDF
DOWNLOAD PDF Original pageKeywords: Genetic Algorithms | NP Hard Problem | Artificial Intelligence | Post Correspondence Problem | Non Deterministic Problems.
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.
