This is an additional post I just posted on Facebook:
Just started to think more about the P=?NP problem.
We already know this:
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
but we're not sure if the inclusions are proper or not. But we do know that
P != EXPTIME, so at least there is one proper inclusion somewhere between
there. This latter result is called the Deterministic Time Hierarchy
Theorem, and its proof uses the technique of diagonalizatio
n
[1].
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. He then, via a tricky but convincing argument, continued to count
beyond infinity and created an unbounded hierarchy of inconceivably large
infinite cardinal numbers (we actually run out of mathematical notations
for such cardinal numbers). He also asked the question that is now known as
the Continuum Hypothesis, in 1875 (resolved by Paul Cohen in 1963).
A generation later, Godel used the same diagonal argument to prove the
famous incompleteness theorem, ie, that all logical systems powerful enough
to axiomatize arithmetics will have theorems that can neither be proved or
disproved within the system. His trick was to assign natural numbers to
logic formulas ("arithmetization"), and then apply the diagonal argument.
Now P != EXPTIME is also proved using the diagonal argument. It involves
constructing a Turing machine that simulates other Turing machines. The key
to the diagonal argument is a set-theoretic term {x | x ∉ Px}, ie, a
predicate P that defines a set whose elements are *not* P.
Reference: [1] "Automata, computability, and complexity theory and
applications" by Elaine Rich 2009
-------------------------------------------
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
