Jeff Rubard
2010-02-06 18:56:14 UTC
P and NP: The State of the Art
Material culled from a series of emails sent on June 17, based on work
done a year ago:
It is rather obvious that model theory was invented in the fabulous
’30s, by the man who later coined the term “theory of models” and
wrote further works on the topic philosophers don’t read since it
“wouldn’t do”. I think the pudding-proof is that the Completeness
Theorem — of which Loewenheim-Skolem (a deliciously Teutonic
hyphenated name) is a consequence when you really understand what it
says — is not really a model-theoretic result.
The model-theoretic idiom in which the completeness theorem was cast
(what’s his name and what was he about?) partially conceals that it’s
just a consequence of the structure of the first-order proof system;
if you doubt this, consider Kalmar’s proof for propositional
completeness. We need model theory for limitative results (!) like non-
arithmeticality, incompleteness, and maybe even the very unheimlich
undecidability theorem (oh, if we cast the problem in that language of
“productions” that mysteriously appeared at some point, I guess not).
Recent results suggest a vast preponderance of oracles make P unequal
to NP; You Know This. What does this finding in “empirical
mathematics” mean? I thought it meant this: the P and NP problem can
be solved negatively not only because of the obvious observation about
a proposition of n literals having n^2 combinations of stipulatively
independent truth-values, but also BECAUSE THE CONTINUUM HYPOTHESIS IS
UNSOLVABLE. “Sometimes you can put a 2^aleph-null set (the oracularly
solvable SAT) and an aleph-null set in one-one correspondence, but
most of the time you can’t.”
What could that even mean? That you are confused when you think you
can do this, like people who believe in the Rebus of Picardy ‘cuz they
read about it in Vico — or just ‘cuz. The “reducible” set of real
cardinality, “solvable SAT”, is fake: if P=NP you already know the
answers regarding satisfiability you would otherwise have to work out
nondeterministically like any old validity testing in propositional
logic, you just don’t know that you know them for whatever reason
(including, I suppose, that it is lucrative to be confuséd).
To be crystal-clear about something you already understand better than
me, what I am saying is this: it is a reductio that P cannot equal NP
because it would mean the end of logic and the end of the world;
strictly speaking, the oracles that permit P=NP reduce the level of
propositional complexity by one order to the cardinality 2^aleph-null-
minus-one, which it is well known is equipollent to aleph-null. This
is a husteron proteron. Furthermore, that people who float the idea
that 99% of oracles are in the first class and one percent are in the
second are in total possession of the true meaning of what they say is
dubious: they could be schizophrenic, or in love.
UPDATE 6/29/09-6/30/09: If people are still “curious”, let me give my
reply to the objection to P != NP from “oracles”. For those that don’t
know, an oracle in computation/recursion theory is a database of
computations (states of a Turing machine, or instructions for another
model of computation) that a regular computer can “query” and use to
determine its next state. Although “oracle machines” can solve
problems that unrelativized TMs cannot, like the Halting problem, they
stricto sensu do not change the complexity of a problem.
How do oracles touch the question of SAT? Like this: an oracle for a
satisfiability-prover is essentially equivalent to quantifiers for a
first-order language built upon the sentences of propositional logic
being quantified over; a clue as to this is given in the first edition
of Hopcroft and Ullman, where the oracle used to “prove” P=NP contains
the set of all true quantified Boolean sentences. How can first-order
logic and propositional logic interact? Well, the Henkin-style proofs
of completeness for first-order logic involve “scapegoat” theories,
where every sentence involving quantification is reduced to an
existentially quantified sentence and then cashed out in terms of the
propositional sentences that satisfy it.
In categorial terms, an oracle is a “subobject classifier” mapping an
n-tuple onto a truth-value; as previously mentioned here, adding
subobject classifiers to a cartesian closed category (the categorial
model of computability) creates an elementary topos capable of
modeling first-order logic. What’s the catch for SAT? Firstly, the set
of true sentences of predicate logic is recursively enumerable, not
recursive: an algorithm can “eventually” produce all its truths, but
no algorithm can discover all the sentences invalid in predicate
logic.
Secondly, an oracle that can be applied to SAT to make P=NP come out
true is, as mentioned above, a device that reduces the complexity of
the proposition being considered by one order – putting it within
(well within) the class of transfinite numbers with a cardinality
equal to that of the natural numbers. I find the most intuitive way to
think about this is of an oracle containing the truth-value of every
“literal” in the proposition under consideration, which adds just
enough “randomness” for the proof procedure to be deterministic and in
P from there on out; you could also think of an oracle machine, using
quantified formulae, which solved the validity of the SAT sentence’s
negation.
Thirdly, as Löwenheim-Skolem (an essential part of Lindström’s
Theorem) shows any set of sentences that has a model — that is, an
interpretation where all theorems are represented — has a countable
model, i.e. one whose elements are recursively enumerable like the
natural numbers they correspond to; “richer” models of computation
have a level of complexity which is, well, too complex. At any rate,
oracles are not enough to override our overwhelming impression that P
cannot equal NP; as for “natural proofs” and other recent
developments, I like functional and complete propositional logic
better than, well…
---- [*fixité*]
~ by jeffrubard on June 20, 2009.
"In another land..."
Material culled from a series of emails sent on June 17, based on work
done a year ago:
It is rather obvious that model theory was invented in the fabulous
’30s, by the man who later coined the term “theory of models” and
wrote further works on the topic philosophers don’t read since it
“wouldn’t do”. I think the pudding-proof is that the Completeness
Theorem — of which Loewenheim-Skolem (a deliciously Teutonic
hyphenated name) is a consequence when you really understand what it
says — is not really a model-theoretic result.
The model-theoretic idiom in which the completeness theorem was cast
(what’s his name and what was he about?) partially conceals that it’s
just a consequence of the structure of the first-order proof system;
if you doubt this, consider Kalmar’s proof for propositional
completeness. We need model theory for limitative results (!) like non-
arithmeticality, incompleteness, and maybe even the very unheimlich
undecidability theorem (oh, if we cast the problem in that language of
“productions” that mysteriously appeared at some point, I guess not).
Recent results suggest a vast preponderance of oracles make P unequal
to NP; You Know This. What does this finding in “empirical
mathematics” mean? I thought it meant this: the P and NP problem can
be solved negatively not only because of the obvious observation about
a proposition of n literals having n^2 combinations of stipulatively
independent truth-values, but also BECAUSE THE CONTINUUM HYPOTHESIS IS
UNSOLVABLE. “Sometimes you can put a 2^aleph-null set (the oracularly
solvable SAT) and an aleph-null set in one-one correspondence, but
most of the time you can’t.”
What could that even mean? That you are confused when you think you
can do this, like people who believe in the Rebus of Picardy ‘cuz they
read about it in Vico — or just ‘cuz. The “reducible” set of real
cardinality, “solvable SAT”, is fake: if P=NP you already know the
answers regarding satisfiability you would otherwise have to work out
nondeterministically like any old validity testing in propositional
logic, you just don’t know that you know them for whatever reason
(including, I suppose, that it is lucrative to be confuséd).
To be crystal-clear about something you already understand better than
me, what I am saying is this: it is a reductio that P cannot equal NP
because it would mean the end of logic and the end of the world;
strictly speaking, the oracles that permit P=NP reduce the level of
propositional complexity by one order to the cardinality 2^aleph-null-
minus-one, which it is well known is equipollent to aleph-null. This
is a husteron proteron. Furthermore, that people who float the idea
that 99% of oracles are in the first class and one percent are in the
second are in total possession of the true meaning of what they say is
dubious: they could be schizophrenic, or in love.
UPDATE 6/29/09-6/30/09: If people are still “curious”, let me give my
reply to the objection to P != NP from “oracles”. For those that don’t
know, an oracle in computation/recursion theory is a database of
computations (states of a Turing machine, or instructions for another
model of computation) that a regular computer can “query” and use to
determine its next state. Although “oracle machines” can solve
problems that unrelativized TMs cannot, like the Halting problem, they
stricto sensu do not change the complexity of a problem.
How do oracles touch the question of SAT? Like this: an oracle for a
satisfiability-prover is essentially equivalent to quantifiers for a
first-order language built upon the sentences of propositional logic
being quantified over; a clue as to this is given in the first edition
of Hopcroft and Ullman, where the oracle used to “prove” P=NP contains
the set of all true quantified Boolean sentences. How can first-order
logic and propositional logic interact? Well, the Henkin-style proofs
of completeness for first-order logic involve “scapegoat” theories,
where every sentence involving quantification is reduced to an
existentially quantified sentence and then cashed out in terms of the
propositional sentences that satisfy it.
In categorial terms, an oracle is a “subobject classifier” mapping an
n-tuple onto a truth-value; as previously mentioned here, adding
subobject classifiers to a cartesian closed category (the categorial
model of computability) creates an elementary topos capable of
modeling first-order logic. What’s the catch for SAT? Firstly, the set
of true sentences of predicate logic is recursively enumerable, not
recursive: an algorithm can “eventually” produce all its truths, but
no algorithm can discover all the sentences invalid in predicate
logic.
Secondly, an oracle that can be applied to SAT to make P=NP come out
true is, as mentioned above, a device that reduces the complexity of
the proposition being considered by one order – putting it within
(well within) the class of transfinite numbers with a cardinality
equal to that of the natural numbers. I find the most intuitive way to
think about this is of an oracle containing the truth-value of every
“literal” in the proposition under consideration, which adds just
enough “randomness” for the proof procedure to be deterministic and in
P from there on out; you could also think of an oracle machine, using
quantified formulae, which solved the validity of the SAT sentence’s
negation.
Thirdly, as Löwenheim-Skolem (an essential part of Lindström’s
Theorem) shows any set of sentences that has a model — that is, an
interpretation where all theorems are represented — has a countable
model, i.e. one whose elements are recursively enumerable like the
natural numbers they correspond to; “richer” models of computation
have a level of complexity which is, well, too complex. At any rate,
oracles are not enough to override our overwhelming impression that P
cannot equal NP; as for “natural proofs” and other recent
developments, I like functional and complete propositional logic
better than, well…
---- [*fixité*]
~ by jeffrubard on June 20, 2009.
"In another land..."