Computability - Complexity - Muse
Casey Hawthorne
state a problem that is not computable.
I've often wondered why is doesn't take a paragraph, at least.
Similarly, with complexity, why doesn't it take at least a paragraph
to describe a problem that is in NP, or in a worse complexity class?
Why should there be all these real world optimization problems in NP,
that would be great to solve in polynomial time, and yet there seems
to be such a wide gulf between P and NP?
It would seem as if tractable real world optimization requires more
than what the Church-Turing thesis says is computable.
So, it would seem as if a proof of P /= NP (or P = NP) would also
require a formal proof of the Church-Turing thesis, which is widely
accepted but not proven.
--
Regards,
Casey
Tim Little
> What has always amazed me, is that in one or two sentences one can
> state a problem that is not computable.
But how many textbooks are required to explain the formal meaning of
the terms used in those sentences? One could likewise call the
Halting Problem "H", and express amazement that one could state an
uncomputable problem in a single symbol.
> So, it would seem as if a proof of P /= NP (or P = NP) would also
> require a formal proof of the Church-Turing thesis, which is widely
> accepted but not proven.
The Church-Turing Thesis isn't sufficiently well specified to admit
proof. Furthermore, it's really more of a physical hypothesis than a
mathematical one: that the physical world does not admit means for
calculating that exceed the power of Turing machines.
In theory there certainly are computational systems more powerful than
Turing machines.
- Tim
Patricia Shanahan
> What has always amazed me, is that in one or two sentences one can
> state a problem that is not computable.
>
> I've often wondered why is doesn't take a paragraph, at least.
Why should it? Mathematicians have put a lot of effort into defining
terminology and notation that lets them say important things succinctly.
> Similarly, with complexity, why doesn't it take at least a paragraph
> to describe a problem that is in NP, or in a worse complexity class?
>
> Why should there be all these real world optimization problems in NP,
> that would be great to solve in polynomial time, and yet there seems
> to be such a wide gulf between P and NP?
>
> It would seem as if tractable real world optimization requires more
> than what the Church-Turing thesis says is computable.
>
> So, it would seem as if a proof of P /= NP (or P = NP) would also
> require a formal proof of the Church-Turing thesis, which is widely
> accepted but not proven.
P and NP are both defined in terms of Turing machines. How can the truth
or falsity of the Church-Turing thesis have any effect at all, either
way, on the relationship between them?
Patricia