I have been examining the NP = P problem and I am wondering, why is proving or disproving NP = P hard? For example, why wouldn't a proof such as the following be adequate? Suppose a million doors were in front of me and I had to discover which door had a red ball behind it. In order to verify the solution, one would have to simply open the hypothesized door. But in order to solve, one must check at least one door to solve the problem. However, statistically speaking, that's like guessing an integer zero to an equation. Therefore, it must take more time to solve, then to check statically speaking, proving P != NP. Although one could argue that they could guess the door, the same goes for any solution to an equation. My question is what is wrong with a proof like the one above?
1
-
$\begingroup$ The chances to solve the P vs NP question without rock-solid command of the basics are probably slim. See here for some primers. $\endgroup$– RaphaelMar 9, 2015 at 8:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The problem is that it's an analogy, not a proof.
- It can't be a proof because it claims to come to a conclusion about Turing machines without using any property of Turing machines.
- $\mathrm{P} \overset{?}{=} \mathrm{NP}$ isn't a question of statistics or probabilities.
- You're making the assumption that it's harder to compute a solution than to check one, from which you conclude that it's harder to compute a solution than check one: this is circular.
- The problem you consider is clearly in $\mathrm{P}$: just check every door and see what's behind it. So you couldn't possibly use that problem to distinguish $\mathrm{P}$ from $\mathrm{NP}$. The best you could hope for is distinguishing constant time (check a solution) from linear time (generate one) in some kind of random-access model of computation.
There's lots of information about why the $\mathrm{P}/\mathrm{NP}$ problem is hard in our reference question.
answered Mar 8, 2015 at 23:33