On Tue, Feb 25, 2014 at 2:36 AM, YKY (Yan King Yin, 甄景贤) <[email protected]> wrote: > Georg Cantor, the father of set theory, first used the diagonal argument to > prove that the rational numbers are uncountable, ie, that the cardinal number > of rational numbers is bigger than the cardinal number of the integers.
Real numbers, not rational. There is a 1:1 mapping between rational numbers and integers. Specifically, numbers of the form a/b can be ordered by increasing a+b and then by increasing a. With regard to the human brain solving NP-complete problems, it may seem that most problems are easy because they are either over-constrained or under-constrained. It is only the small set of problems near the boundary that are hard. For example, the traveling salesman problem asks if there is a cycle through all the vertices of a graph G whose labeled edges sum to less than D. If D is very large, then it is easy to find a satisfying path. If D is very small then it is easy to prove that the answer is no (for example, D is smaller than the distance between two vertices). It is only when D is near the best solution that the problem gets hard. -- -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
