On Wed, Feb 26, 2014 at 11:05 AM, Matt Mahoney <[email protected]>wrote:
> 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. > Thanks for the correction =) > 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. > Yes, that is the "phase transition" phenomena observed in some combinatorial problems, such as SAT: http://cstheory.stackexchange.com/questions/14953/current-tightest-bounds-for-critical-3-sat-density Also, the number of instances of SAT problems (3-SAT, anyway) for each N, is actually finite and quite small: http://cstheory.stackexchange.com/questions/2168/how-many-instances-of-3-sat-are-satisfiable?rq=1 This fact may be helpful in defining approximation -- as probability distributions over such discrete, finite spaces. ------------------------------------------- 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
