Hat Trick

I have some idea that the computer science community, which even writes in English worldwide, has gotten the notion via someone or other’s writing on the P and NP problem (forever solved negatively, at the cost of also solving one of the greatest problems of mathematics ever) that “you’re never gonna stop all the teenage leather” – and adult leather is kind of wahnsinnige. However, I would like to say something further: Mahatma Ghandi was one of the worst people who ever lived; and his only effective British critic, “George Orwell”, rather better. Ghandi wanted everyone to live, that is die, that is die fast under horrible circumstances amidst undistributed plenty; Orwell wanted everyone to die, that is some people to die, the right people to die, the fewest possible people to die.

My contribution to the debate? Ghandi said that Hindustan and Pakistan were the two “eyes of India”: I say, to myself if necessary that like “Blinky” on the Simpsons, theoretical logic has three eyes — proof theory, model theory, and recursion theory. Any genuine logical result is perfectly intertranslatable between the three logical idioms; anything less is “philosophical logic”, an attempt to understand why you don’t understand, why it has to be some way you don’t know it is, because you can’t know it is, because it isn’t. To conclude abrupto, Anil Gupta’s “revision theory of truth” is Anil Gupta’s, that is John Nash’s: they are friends, I guess, and Nash explained his view of the world to Gupta and unlike Nash Gupta found it simpatico. But inasmuch as ye have done it unto one of the least of these my brethren, don’t forget that Woodrow Wilson was a hophead.

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…

Mathematics and Human Interests

Now, for a piece of philosophy of mathematics. It’s hard to see how you could take a “sideways-on” approach to mathematics: it is true if anything is, right? Well, maybe we can stretch that out a little further than what is involved in the usual Third Realm calisthenics. A piece of mathematics is something that will be true for all time: mathematical insight means seeing into the ages, what was and ever will be. Conversely, lack of mathematical acuity — our inability to solve a problem — is caused by the deceptions of the age, our follies and delusions.

As regards my own very modest mathematical output, I have adduced considerations that P cannot equal NP in ”A Cool Million (Some Thoughts on P and NP)”, ”Further Thoughts on P and NP“, and ”Why P Cannot Equal NP“. They do not have the form of a formal proof and have failed to convince the contemporary complexity community (as a whole), but it is my honest conviction that the very simple logical difficulties associated with reducing the complexity of DEXPTIME-hard NP-complete problems are insuperable. The considerations are “dumb”, but honestly limitative results always are — the Incompleteness Theorem is a piece of simple trickery that would hold no interest were it not true.

Really, I think the hope that a brand new algorithm will crack the problem is a pipe dream; the essential nondeterminacy of the Satisfiability problem is just untouchable. Why does it appeal, then? Because computer science is about technical control, and the temptation of a computational Eden where all cryptographic algorithms can be cracked and mathematical proofs grow on trees is just too strong. (The harder-headed claim that problems from oracles — which are rather moldy, as they can be read about in the original edition of Hopcroft and Ullman – and other considerations may make the P and NP question impossible to solve, but it may just be our own damn fault for not defining our terms clearly. Always hard to tell.)

Long Tall Sallies (Amazon Deals)

Before blogs really got off the ground, I spent my days (!) writing ‘experimental’ reviews of books on Amazon. Often I had no very good idea of what the book was about, and even when I did many people thought I did a very poor job conveying it; I’ve only recently brought my favorable/unfavorable response ratio to 1:1. Furthermore, nobody but nobody has ever bought me anything off my Amazon Wish List — this is too bad, because a couple of the selections are very attractively priced, so much so that the unionized Powell’s employees a lot of people want to help out with online purchases would just tell you to “go for it” (they’re not talking to me, long story).

Here are three selections:

Wilfrid Hodges, Model Theory (paperback)

‘High-test’ logic textbooks are often incredibly expensive: as previously mentioned Cambridge’s theoretical computer science series is reasonable, but North-Holland/Elsevier, Springer, and Oxford books easily can cost $200 apiece. The same was true of the “big red” model theory textbook from Wilfrid Hodges, which retails at $280 in the hardback edition available since 1993 but now costs only $64.80 in the paperback edition released this year, just a little more than the extracts from the book published as A Shorter Model Theory. Hodges takes a more mathematical — specifically, algebraic – approach to model theory than the old standby by Chang and Keisler, but at this price you can afford to be (slightly) fashionable.

Friedrich Nietzsche, Sämtliche Werke: Kritischen Studienausgabe (15 vol box set)

I’m no big fan of Nietzsche, but the over-reliance on tendentious interpretations surely does those of us being subjected to “perspectival thinking” and “ethical naturalism” by intellectual rounders no favors. The student with a grasp of German and a reasonable budget for scholarly books need not take das Wort of  Walter Kaufmann, R.J. Hollingdale, or anyone more recent about Nietzsche’s ideas, since the complete edition of his works and notes compiled by Colli and Montinari — though purged of some critical apparatus for the student edition – is available for under 200 dollars; as a reviewer points out, this works out to something like $12.50 a volume (their figure is lower; it used to be an even better deal, but the dollar’s slide against the Euro intervened). In particular, the material in Colli-Montinari vol. VIII (selections from which made up the Wille zur Macht and Kate Sturge’s recent Writings from the Late Notebooks) is very interesting and very different from what one might expect.

Various Artists, The Complete Stax-Volt Singles Vol. 2 (9 CDs)

This is one I’ve been waiting on a long time; long enough, in fact, for most of the material to become available free on the Internet. But artists need your money, just like Stax artists did when they sold the rights to their ’60s hits at the end of the decade and had to record a lot of new material very quickly (this box set covers only three years). Surprise, surprise: a lot of these records – like Lynda Lyndell’s “What A Man”, Jean Knight’s “Mr. Big Stuff”, and Eddie Floyd’s “I’ve Never Found A Girl (To Love Me Like You Do)” — were instant classics. The first box set is in your public library; the second should be in somebody’s stocking.

Subjects for Further Research

1) Is forcing a model of the full resolution calculus? That forcing statements are written with a double turnstile suggests it was originally intended as a semantics of something; resolution seems to be the neatest proof-theoretic fit to the check of consistency against generic sets (hard to say whether countably transitive models introduce more structure than first-order resolution can account for, though).

UPDATE: The answer to this question is “Duh, no, since forcing creates models of ZF”. Alternate suggestion: perhaps Gentzen’s “reduction rules” for proving the consistency of arithmetic with methods stronger than those of ordinary logic are a better fit.

2) Do Lindström’s theorem and the “standard translation” of modal logics into first-order logic suggest first-order logic is the most expressive complete logic? The “negative translation” of classical logic into intuitionistic logic seems to suggest otherwise, but the completeness of IPC is a thorny thicket. (I must admit ignorance of completeness w.r.t. languages with generalized quantifiers, although they certainly do not fit Lindström’s characterization.)

3) What is the semantical status of cut-elimination proofs? We know by Guessing What Great Logicians Thought that they are not proof-theoretical analogues of completeness proofs, since completeness proofs for sequent calculi (e.g., Kleene’s) do not operate on the same principles. How about soundness? Cut-elimination demonstrates that inferences introduced by an “irregular” procedure, an instance of the cutrule, can be proven using more strictly regimented rules — in other words, that the cut-free rules suffice to justify the Urform of an inference justified any old way (Cut).

A Thought

I always thought one of the more interesting and relatively unremarked-upon elements of the Philosophical Investigations was the item included in the Preface after Wittgenstein’s thanks to Ramsey:

Even more than this — always certain and forcible — criticism I am indebted to that which a certain lecturer at this university, Mr P. Sraffa, for many years unceasingly practiced on my thoughts. I am indebted to this stimulus for the most consequential ideas of this book.

(For those who don’t know “P. Sraffa” was Piero Sraffa, editor of Ricardo’s collected works and a Marxist economist; he and Wittgenstein were great friends, partially because he was as Keynes said “the most leisured man who ever lived”. He also holds the distinction of having purchased the books which Gramsci’s Prison Notebooks are commentaries on.)

However, do you suppose Wittgenstein’s later work was also in part insipred by a reaction to the rise of Tarskian semantics similar to C.S. Lewis’ famous reaction to Anscombe’s dinner-table refutation: the idea that someone had “sharpened” one’s own theses to the point they pointed in the opposite direction, and that the thing to do was concentrate on something one knew better?

Formal and Transcendental Logic

Here’s a revision of something I said a while back. Kant famously made a division between “general logic”, which deals with the structure of all argument, and “transcendental logic”, which addresses the conditions of experience. However, if you seriously think about it, formal logic has a transcendental structure: metalogic is composed of transcendental arguments. We have objects and structure (model theory), and rules of proof that allow us to navigate the objects and structure: each must be adequate to the other, the model-theoretic structure representing all consequences of the proof calculus and the proof calculus sophisticated enough to “reach” all points of the structure. It really makes no sense to be a “model-theoretic realist”, even a “modal realist”: logical structure must be completely expressed in proof. It makes no sense to be a “proof semanticist”: logical argument that does not eventuate in conclusions is not argument, and those conclusions just have mathematical structure that “falls out”. We must be “transcendental idealists” about the underpinnings of proof (i.e., the rules are coherent as organizing principles) and “empirical realists” about the determinacy of statements (we just don’t know better).

Mythologies of Reason

First I will speak here of an idea which, as far as I know, has not occurred to anyone. We need a new mythology, however, this mythology must be at the service of the ideas, it must be a mythology of reason.

Hegel or Schelling or Hölderlin, “The Oldest System Program of German Idealism”

Now, a logical word about Freudianism. Recently I cast doubt on the ability of relatively recent “computational theories of mind” to adequately account for mindedness, but one need not “stay current” to see why this might be so: we find this dialectic already in Freud. As is well-known, Freud began his work as a neurologist studying with Charcot, and his 1895 “Project for a Scientific Psychology” outlines a proto-neuroscientific theory of the mind. However, shortly thereafter he left the nerves behind and began working in the metier we know him in: the scientific hermeneut, whose theories of drives and the symbolic essences of psychopathology are at least almost as interesting for the literary theorist as for the practicing clinician.

Obviously the neurosciences have improved since the days of Ramon y Cajal staining brain cells with silver chromate; why would we think that Freud’s compensation for their inadequacy then would hold any interest today? Well, perhaps the Freudian orbit that cannot be escaped is his modernist project of a scientific mythology, a “theory of mind” that adequates mental states to potential scientific reality, to what can reasonably be conjectured to be the case. In mapping psychological distress onto biological states and personal histories very widely construed, Freud traced the inside of reason, through elaborating processes of “radical interpretation” that do not transgress reason’s modesty about its epistemic abilities and pragmatic powers.

So this “scientific mythology” is not only scientific, it is a mythology: an attempt to map the entire space of signification, to include all possible configurations of sense. Now, in formal logic, all possible configurations of sense (“modes of presentation”) are included in the intensional logic based on Russell’s theory of types; I offered a very rudimentary elaboration of this in my discussion of Montague Grammar, and do not want to elaborate the whys and wherefores much further at this point except to note the presence in symbolic descriptions of the hierarchy of types by other writers of the lower-case a to denote the “extensions” senses are mapped onto.

The theory of types, like any other logic powerful enough to generate Peano Arithmetic, is incomplete: there cannot be a finite axiom set capable of deriving all its truths. But there’s at least a little confusion about why this is so, and so I’d like to talk about some elements of Gödel’s proof which are less commonly dwelled on. A lot of people are familiar with the idea of Gödel numbering, which assigns a logical statement a unique number by encoding each of its symbolic constituents: figuring out the point of Gödel numbering is a little harder. Complete logics have a primitive recursive axiom set: that means that the theorems which are provable depend on the theorems that have already been proven, going back to “base cases” instantiating a finite set of axioms.

Primitive recursion is a concept in the theory of computation: the primitive recursive number-theoretic functions are a subset of the computable functions. If we give each sentence a Gödel number and the predicate “is the Gödel number of a theorem of L” is primitively recursively definable, the logic is complete. The first incompleteness theorem shows this is not possible. If that predicate was primitively recursively definable, there could be a “fixed-point theorem” stating that any theorem mutually implied the number-theoretic representation of the proof of the theorem. Suppose we devise a statement saying “I am unprovable” (that there is no primitively recursive number-theoretic representation of a proof of the statement).

If the logic is consistent this statement will be unprovable, but if the logic is ω-consistent (a statement true of every natural number is true) the statement will be provable (there will be no primitively recursive number-theoretic representation of its proof among the natural numbers). This is not to say that a logic powerful enough to develop Peano arithmetic is necessarily inconsistent, and maybe it is not even to say that its axiom set is not recursive tout court: general recursion includes an additional device, the μ-operator, which searches for the smallest natural number with a certain property: this is equivalent to the “while” or “for” loops in programming languages, but perhaps it is also equivalent to simply adding a new axiom when we find a mathematical truth that cannot be proven using the axioms we already have.

The point of all this as regards the Freudian import of the theory of types is that there is not a computationally effective procedure for “semantic descent” for defining higher-order abstractions in terms of the more concrete objects they quantify over: but that is not to say that psychological or other abstractions are necessarily inconsistent. We need to work through our symbolic hierarchies and choose wisely in terms of ordering principles, and what would that be but a “mythology of reason”?

Vocabularies of Physicalism

Though what scientific training I do possess is almost all in the “human sciences”, when I was a young lad I was quite interested in the physical sciences: and though my knowledge of physics isn’t much more advanced than knowing the rudiments of Newtonian mechanics, recently I had a thought about “physicalism” and the fine structure of the language of physics. As the SEP tells us, “Physicalism is the thesis that everything is physical, or as contemporary philosophers put it, that everything supervenes on the physical”: and for most people who fundamentally accept the results of natural science, physicalism is an attractive philosophical position. However, there are some obvious problems with physicalism, one of them being the problem of “theory change”: if the laws of physics limn the structure of fundamental reality, how to explain what happens when those fundamental laws are adjusted, as they frequently are?

Here is my thought, which one might classify as an “anti-realist defense of physicalism”. The language of contemporary physics is actually the most expressive vocabulary humanity possesses: it describes events in the minutest detail, since it possesses logical resources far in excess of the “special sciences” and “common sense”. Putting a fine point on this is hard to do: perhaps the logic of string theory is a very “multi-dimensional modal logic”, one which the simpler logics of Einstein, Bohr, and Newton (not to mention Marx, Nietzsche and Freud) can be embedded in. But, whatever model of physical reality is standard for you and however you gloss its logical articulation, accepting a supervenience thesis is tantamount to saying that the supervenient vocabulary is not powerful enough to distinguish base states, while the base vocabulary is powerful enough to distinguish supervenient states.

Really, I think that any kind of “empirical realism” about the physical world tends towards such a supervenience thesis: if you don’t accept physics as determinative, you are ultimately not accepting it at all, opting for an unscientific world of miracles or flux. However, this raises another perennial problem of physicalism: why have special sciences and common knowledges at all? If physics is the ultimate vocabulary, why talk about anything any other way? Well, if there are atoms (or electrons, or quarks, or strings) there is also the void, and although I don’t think this is quite what Badiou means by the term we can say that special sciences are “subtractive ontologies”: since we know that our physics (or any physics ever) is not complete, does not describe the workings of the universe in absolute detail, we cannot be Laplacian demons: we opt for restricted vocabularies which accept that sometimes the standard of precision appropriate to understanding a phenomenon is more or less that of being “good enough for government work”.

Sometimes our purposes in understanding a phenomenon are purposes, do involve an element of interest rather than pure “wonder”. So even though the special sciences must exist in a base-superstructure relationship to physical theory (until they become a part of physical theory, as with chemistry) expecting that we must always get “clearer” concerning things which our volitions about are none too clear is some kind of bargain, and not necessarily one worth making.

Why P Cannot Equal NP

I recently started a conversation on comp.theory with this post:

Newsgroups: comp.theory From: jeffrub…@gmail.com Date: Tue, 17 Jun 2008 13:02:09 -0700 (PDT) Local: Tues, Jun 17 2008 1:02 pm Subject: P does not equal NP – a logical approach Hey, do you guys want to hear a good one? The structure of Satisfiability shows that NP-complete problems cannot be simulated in P without oracles. Here’s how: n propositional atoms can have 2^n different sets of truth-values. For an n-atom statement (it could be in CNF, although it makes no difference) any one of those 2^n lines in its “truth-table” could satisfy it: and since each of those permutations is independent of the others by definition (no truth value of an atom can depend in any way on the truth-value of any others), the upper bound on a deterministic search for a satisfying set of truth-values must be 2^n. Oracles work (or don’t work) by reducing the truth-functional complexity under consideration to 2^n-1: the mathematically inclined among you will notice this is ever so slightly less than the cardinality of the power set. But that’s a story for another time.

——

Once people figured out what I meant, more or less, I was told that the observation about truth-tables was commonplace and the conjecture about oracles confusing to the point of uselessness. Unfortunately for scientific elegance, however, this observation (reformulated a couple of different ways) is the reason why P does not equal NP. Here’s one reformulation: the paper-and-pencil algorithm for testing satisfiability involves the backwards reconstruction of a prooftree for the sentence of propositional logic under consideration.

There are 2^n possible prooftrees (modulo truth-functionally equivalent symbolic formulations), since there are 2^n possible assignments of variables and the next level of a prooftree compositionally depends on those assignments, and so on. Using paper and pencil, we “sweep through” these possible prooftrees by nondeterministically guessing valuations and eliminating other valuations incompatible with the guess: but if we don’t guess, we can’t eliminate (since any of the prooftrees may be a correct one). A nondeterministic automaton moving through a “tableau”, as in Sipser, does the same thing (using the multiple possible transitions associated with a state in the nondeterministic automaton).

There is no way to translate those multiple transitions (which, taken together, must comprise the power set of n, all possible combinations of n variables) into the single transitions of a deterministic automaton faster than 2^n. Deterministically considered, SAT is EXPTIME-hard for unrelativized TMs.