
Re: On NP Completeness and Intractability
Posted:
Nov 1, 2005 8:08 PM


In article <5cS9f.67708$yS6.29523@clgrps12>, Oliver Wong <owong@castortech.com> wrote: > >"Googmeister" <googmeister@gmail.com> wrote in message >news:1130841412.361815.26090@g47g2000cwa.googlegroups.com... >> Oliver Wong wrote: >>> "Googmeister" <googmeister@gmail.com> wrote in message >>> news:1130280233.852612.195060@f14g2000cwb.googlegroups.com... >>> > >>> > No, actually most decision problems are undecidable. There are >>> > countably >>> > many Turing machines (like the integers), but uncountably many decision >>> > problems (like the real numbers). Hence, virtually all decision >>> > problems >>> > are undecidable. >>> >>> I'm curious to know  can you explain how you know (perhaps via a >>> formal >>> or informal proof) that there are uncountable many decision problems? >> >> Formally, a decision problem is a subset of strings over some alphabet, >> say the binary alphabet. There are uncountably many such subsets. > > Couldn't you list all the binary strings of length 1, then of length 2, >then of length 3 and so on, thus iterating over all binary strings and thus >all decision problems?
You can iterate over the strings, but not over the subsets of strings.
> Or equivalently, assuming that an decision problem can always be >described in English (e.g. using an alphabet of 26 characters, 10 digits, >and some punctuation), couldn't you iterate over every possible ASCII >sequence and thus "count" the decision problems?
Your assumption is false. Only countably many sets of strings, and therefore only countably many decision problems, can be uniquely described in any particular language with a finite alphabet.
Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada

