Contributed by The Goedel Turing Society of India
THE CREATION OF A MONSTER--THE SEEMINGLY INTRACTABLE NP-COMPLETE PROBLEMS
DOTHEBOYS HALL REVISITED
COOK’S THEOREM DEMYSTIFIED
[To easily grasp the ‘Big Picture’ of the construction involved in the famous Cook’s Theorem has proved to be a great hurdle in the study of the P=NP problem. Here a common sense rendering of Cook’s Theorem with a touch of formalism is attempted.The rendering is to be taken with a deep sense of humour and no levity is meant. The aim is to present and grasp the ‘flavour’ of the ‘Big Picture’ involved in the construction in a user-friendly manner to audiences in pre-agrarian and agrarian environments with minimal computer science or software jargon. However, what may be considered common sense, common knowledge and an acceptable way of life in some environments may sound strange, scandalous and offensive in some other environments. The description with modifications and variants has been successfully used for about three to four decades as cultural background in formal, semi-formal and informal training and educational programs. The entire construction mirrors the construction as in standard texts in the area of Algorithms.
Another aim of the study is to explore why in many diverse activities and walks of life in Utopia the creation of comprehensive make believe documentation that an activity has been carried out is given great importance but the activity itself does not or may not take place, rather it is only simulated. This seems to be related to the concept that the culture of Utopia is essentially that of a Land of Verifiers. That is why Utopia takes to outsourcing in our Solar System as a fish takes to water.
The famous P=NP question is related to the question whether Solvers of Problems in NP are necessarily involved in a higher level of intellectual activity than the Verifiers of Solutions in NP. Recent studies by Pooh and his friends seem to indicate otherwise.They feel that P=NP and Solvers and Verifiers are essentially involved in equally easy or equally difficult intellectual activities when the problem space is restricted to NP.It turns out that the activities of Solvers and Verifiers complement each other in large projects.]
OPEN THE LINKS BELOW IN A PRIVATE WINDOW
THE CREATION OF A MONSTER---COOK’S THEOREM
A NP-COMPLETE PROBLEM BY SIMULATION OF A NDTM OF POLYNOMIAL TIME