theory about p, np problems

I am reading about P , NP and NP-Complete 开发者_开发问答problems theory. Here is text snippet.

The class NP includes all problems that have polynomial-time solutions, since obviously the solution provides a check. One would expect that since it is so much easier to check an answer than to come up with one from scratch, there would be problems in NP that do not have polynomial-time solutions. To date no such problem has been found, so it is entirely possible, though not considered likely by experts, that nondeterminism is not such an important improvement. The problem is that proving exponential lower bounds is an extremely difficult task. The information theory bound technique, which we used to show that sorting requires (n log n) comparisons, does not seem to be adequate for the task, because the decision trees are not nearly large enough.

My question is what does author mean by

1. by statement "To date no such problem has been found, so it is entirely possible, though not considered likely by experts, that nondeterminism is not such an important improvement." ?

2. Another question what does author mean by in last statement by "because the decision trees are not nearly large enough." ?

Thanks!

---

(1) I think the author means that no NP problem has been found, for which it is proven that it is not in P. Certainly there are problems in NP for which no polynomial solution is known, but that's not the same as knowing that none exists.

If in fact P = NP (that is to say, if in fact there are no NP problems that don't have a polynomial solution), then in some sense a nondeterministic machine is no "more powerful" than a deterministic machine, since they solve the same problems in polynomial time. Then we'd say "nondeterminism is not such an important improvement".

(2) The way that the n log n proof works is that there are n! possible outputs from a sorting function, any one of which might be the correct one according to what order the input was in. Each comparison adds a two-legged branch to the tree of all possible states that a given comparison sort algorithm can get into. In order to sort any input, this "decision tree" must have enough branches to produce any of the n! possible re-orderings of the input, and hence there must be at least log(n!) comparisons. So, the lower bound on runtime comes from the size of the tree.

The author is saying that there are no known NP problems for which we've proved they require a tree so large that it implies a lower bound that is super-polynomial. Any such proof would prove P != NP.

---

1. The Author gives the possibility of someone may come up with a solution to NP-Complete problems that is not exponential time.

2. The second part is little vague, he seems so that the lower bound of search tree which we all agree to be O(n log n) is by information theory and if we use large decision trees, which can furture reduce the lower bounds. This is really vague.

BTW, of all the introductions to NP related buzzword explainations, I find this super confusing, which book/ chapter is this from?

A good text is Micheal Sipser's Theory of Computation or listen to Shai Simonson's lectures.