Question: Having received negative press from their recent debunked discoveries, Prof. Allen Touring and Prof.Amy Badele revised their previous work and wish to publish their latest

Having received negative press from their recent debunked discoveries, Prof. Allen Touring and Prof.Amy Badele revised their previous work and wish to publish their latest breakthrough to the world. They once again claim to have proven that P != NP and provide you, their trusted colleague, with their prized manuscript. After reviewing the proof you see that they have done the following:
(a) They defined a new decision problem called the Hamiltonian Count. (The details are irrelevant - just to further the story).
(b) They showed that an instance of the Traveling Salesman Problem, a well-known NP-Complete problem, could be reduced in polynomial time to HamiltonianCount. This took a few pages, but they correctly showed how to take an input for the Traveling Salesman Problem and convert it, in polynomial time, to an input for the HamiltonianCount problem such that the answer for the Hamiltonian Count instance gave the answer for the instance of the Traveling Salesman problem.
(c)They then spend several pages proving that Hamiltonian Count is not in P. That is, Hamiltonian-Count cannot be solved in polynomial time.
(d) But since HamiltonianCount is NP-Complete, and Hamiltonian Count is not in P, then P !=NP.
You realize yet again after reading the full article that their tome has a major flaw in it. Profs. Touring and Badele did not in fact just prove that P != NP. Explain to the Professors where the flaw in their logic lies. (Note, it isn't some hidden flaw. They did something fundamentally wrong in their proof.)

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!