|
|
Re: On NP Completeness and Intractability
Posted:
Nov 1, 2005 5:43 PM
|
|
"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?
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?
- Oliver
|
|
