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 120
- Downloads 0
CLOUD COMPUTING AND ITS PRICING SCHEMES
Cloud computing is a rapidly emerging technology which involves deployment of various services like software, web services and virtualized infrastructure, as a product on public, private or hybrid clouds on lease basis....
Improved Optimal Competitive Hopfield Network for the Maximum Stable Set Problem
A large number of problems in artificial intelligence and other areas of computer science can be viewed as special cases of the Maximum Stable Set Problem (MSSP). In this paper, we propose a new approach to solve the MSS...
An Agent Based Simulation Model for Warning Messages Dissemination in a Vehicular Ad hoc Network
Since the safety on roads has become a main concern for both governments and car manufacturers in the last twenty years, number of applications into the domain of vehicular communication is proposed. Vehicular Ad hoc Net...
Effective Comparison and Evaluation of DES and Rijndael Algorithm (AES)
This paper discusses the effective coding of Rijndael algorithm, Advanced Encryption Standard (AES) in Hardware Description Language, Verilog. In this work we analyze the structure and design of new AES, following three...
Hybrid Neuro-Fuzzy Systems for Software Development Effort Estimation
The major prevailing challenges for Software Projects are Software Estimations like cost estimation, effort estimation, quality estimation and risk analysis. Though there are several algorithmic cost estimation models in...