math monster

1 Reply

hi all. welcome to this new blog.

this blog is partly inspired by, and a tribute and/or dedicated to the P vs NP problem.[7,16]

the goal/intention with this blog will be to keep it fairly focused on complexity theory.[18] the idea will be to post or even “cyber-publish” some of my notes on miscellaneous research directions/topics Ive explored or am looking into. so it will have a strong mathematical and computer scientific flavor/slant/angle. I chose wordpress very much on purpose for the Latex typesetting capability, which is fabulous! Im also intending on posting diagrams and code samples.

but as blogs have a tendency to do, it will maybe (hopefully?) veer off occasionally into misc topics from time to time esp depending on audience/reader response/feedback. however its clear this blog will have a limited audience due to its high specialization. there are other complexity theory blogs with significant audiences or at least bunches of dedicated readers (it amazes me how much response some get in comments) and Ill be linking to those [let me know your favorites in comments!]

best case scenario for me is enthusiastic but not aggressive commenters with a high degree of expertise in the field, ideally PhDs, who can apply a high level of rigor in analysis and review to the ideas and directions and maybe even a few offhand ideas of their own. of course at this early stage thats [wildly?] optimistic, but it does happen on other blogs, and am planning to link to notable and favorite examples.

* * *

here Ill give a brief intro to my related/relevant bkg which Ill maybe expand on later. from a very young age, preteens, I became interested in “difficult theoretical problems” as intense intellectual challenges. this started out in number theory, namely Fermats Last Theorem. it fascinated and astonished me that a question that could be stated in such a simple, basic way could be unresolved for so long (3.5 century!). I could see a kind of austere beauty.

later I dabbled in Hofstadters books[31,32] and this introduced me to the Turing machine which I found deeply engaging also, particularly the halting problem. again I marvelled that such a simple-sounding problem could hide such explosive complexity. “appearances are deceiving”.

the summer right before college I inadvertently introduced myself to complexity theory by reading (an old, maybe original edition of) Sedgewicks book, Algorithms. he had a very brief appendix (close to only 2 pages in my memory) mentioning SAT and the theory of NP completeness. as soon as I got to school I looked for the legendary Usenet and started writing a few neophyte posts on the sci.math and comp.theory newsgroups related to SAT and NP completeness.

I was highly excited to receive replies and emails, some from graduate students (maybe also teaching assistants) at colleges who courteously and generously enjoyed some modest level of cyber-tutoring (the kind of modest altruism you might now find all over on stackexchange—much more on that later). one respondent told me that Sedgewicks Algorithms book was possibly “the worst possible way to learn about NP completeness”.

so for over 2 decades Ive been researching complexity theory as an avocation to varying degrees of dedication. Im especially enamored with and partial to empirical approaches which while somewhat utilized I feel are still somewhat underutilized in the field due to a sort of “theory bias”. to me it is unrivalled in some situations for visualization and in building up intuition.

over the years I have written two scientific papers, both highly mathematical with latex & diagrams, and one quite ambitious, but none in complexity theory.

* * *

yes, there are other blogs already ostensibly dedicated to P vs NP eg RJ Lipton[17] who wrote a related book[19] and seemed to maybe have started his blog to publicize the book. however assuredly this blog will be different.

I toyed with naming this blog “math monster” for various reasons, but then “chickened out” as the slang goes. seriously though I want to try to draw an elite crowd and figured that name might be a bit too off center. but I collected and wrote up these following related ideas anyway.

when I was younger in my early 20s I pictured that math problems were mostly requiring flashes of brilliance. I was very fascinated with proofs in number theory or elsewhere that were highly complex and later simplified. nobody could accurately predict what proofs could be simplified like this. it seemed possible at the time that a P vs NP proof might not be extremely complex. now I realize that some of this was an excuse for avoiding learning difficult, dense theory.

“shortcuts” have fascinated and occasionally obsessed me me from a young age. but in CS it was Brooks who said, “there is no silver bullet”. this even shows up in economics as “the no free lunch theorem” and probably analogously in physics as the thermodynamic law rejecting perpetual motion machines. and my pessimism has grown over the years just as one working in the saltmines of capitalism becomes skeptical or even verging on bitter about “get rich quick” schemes.

as the years have gone on, a simple proof seems extremely unlikely. the problem is now more than 40 years old (which by the way I delight in realizing was conceived not long after the same time I was). many experts in the field did not think it would be this hard either. it now seems it may be as hard as some of the famous hardest problems in mathematics, eg like Lindemanns proof of the irrationality of Pi. modern researchers such as Mulmuley[9] estimate it might take a century of mathematical development starting from *now* to eventually succeed.

and then the huge $7M claymath prizes were announced around ~2000[20] and I thought that the problem might be solved with such a huge $1M incentive. I thought it was a divine sign or superpower synchronicity because Id mentally cringed for many years that the problem had no award and had to be content with fantasizing about some more long-shot kind of post-victory award like a fields medal! [and I was just a few yrs ago newly inelgible for that one!]

it seemed less hard to me than other problems on the list [eg esp riemann conjecture]. and already 1 has been awarded, for the Poincare conjecture (some great books on that now out I need to read and maybe review here). but nearly a decade has gone by and it seems there hasnt even been a “near miss”, or anything close.

when younger I pictured P vs NP like a sort of Everest peak, and others have made the analogy. however, Everest was summitted eventually, and even done so without oxygen. increasingly it seems like P vs NP might be somewhat more analogous to Olympic Mons on Mars, which might be climbed or summitted within a few hundred years! (even if humans go to mars, they may have no interest in summitting Olympic Mons in a near timeframe).

when people say that maybe P vs NP will not be solved in our lifetime, which is not at all implausible given its history so far, it begins to take on a superhuman feel to it. and I feel that psychological analysis is relevant. thinking that one can solve such a difficult problem may relate to ones own narcissism or mania! and working on it for so many years without a lot to show for it can be literally depressing. as the saying goes “fools rush in where angels fear to tread”.

so P vs NP is probably less a mountain to climb at times than a sort of “monster”. others have used this analogy.[6] the analogy is used in mathematics for the classification of finite simple groups where proofs lead to thousands of pages.[30,33] it also shows up in a famous quote by Poincare referring to pathological functions eg the Weierstrauss function.[34] could complexity theory contain similar “beasts”? it seems plausible. the Blum speedup theorem[35] is said to refer to “pathological languages” by at least one authority, Goldreich, in his excellent online book.

on the other hand we also have the saying of “a monster under the bed”. is P vs NP a real monster (eg maybe is it unprovable?) or just a monster under the bed, ie scary but surmountable?[21] when its very hard to prove something, to some degree its reasonable to look for plausible reasons why its so hard, ie a sort of “circuitous route”.[8,11] but it does seem like new proofs may have surpassed older theory.[13]

* * *

in any case I can try to cheer myself up a bit by citing all my favorite references on the subj & some related material and build a nice map for anyone else who wants to try their hand.

Lance Fortnow is a brilliant authority in complexity theory, one of the “alpha males” of the field. [1] is a great summary/survey by him. Allender[15] is also very readable.

its “way cool” the pure mathematicians are getting interested in P vs NP and related areas eg natural proofs [14]. at heart it seems to be related to extremal set theory, something that the now-legendary Erdos was one of the major gunslingers of the 20th century. Gowers the field medalist wrote a neat survey on Razborovs proof[2] where he jokingly referred to Razborovs “near supernatural powers”. the proof is indeed very difficult to follow. I managed to figure it out via Savages book [3] which seems to me an excellent reference in many ways.

Erdos theory of sunflowers[5] shows up in the proof and I feel that this basic mechanism is likely to reappear, esp given that it has been shown to be very similar to the important “switching lemma”. in fact I sometime wish Erdos was still alive so I could propose a collaboration with him and show him how close circuit theory may relate to extremal set/graph theory. one might even call it “extremal circuit theory”! the experts are not so hopeful about circuit theory resolving P vs NP any more but I think this pessimism is misguided.

I think from deep study, circuit theory is the prime and most likely branch of theory that could really “slay the dragon” but probably also with strong contributions/mix from extremal set/graph theory. its a powerful collective mix that can be seen in Razborovs famous proof[22,23] and in my opinion still not fully appreciated. Razborov has a very obscure paper where he proves a negative result of the “power of approximations” and the Alpha Male of the fields opinion and sketchy evidence seems to have had [probably unintentionally] a major, overreactive dampening effect on everyone else, to the point of becoming near urban legend or folklore, in my opinion….

but, I will admit as recent as just the turn of the century [yikes, how is that possible] I was highly skeptical of monotone circuit theory as having much power. that changed dramatically with my understanding of Razborovs theorem and the concept of NP complete slice functions, which is still imho a fairly undeservedly obscure topic in the theory. (in fact [10] is an example of how little attn the field gets- its a fairly trivial question with several reasonable answers eg the entire paper [24], yet unanswered on stackexchange.) not many in the whole world know about it. maybe its “rodney dangerfield” status will change a smidgeon after further blogging on the subject.

…

other ref not mentioned so far. [4] is a with-a-straight-face list of all the crackpot proofs of P vs NP both ways, many on arxiv. [25] is a colorful, educational play dialog between 3 characters on the difficulty of proving complexity theory lower bounds by Gowers.

anyway, really do hope to hear from you in the comments. feedback is probably at least more than half the reason Im starting this blog and it will be the prime determination of how much time/energy I put into it. I plan to write intermittently but will monitor the site closely for comments and probably reply to most comments also.

footnote— holy cow just tried to change the font and apparently wordpress wont let me do that without *paying* for it. @#%$!! hate helvetica but not sure if its actually worth $30/yr to me to chg it! talk about “giving away the razor for free and charging for razor blades”! geez! am having a bad feeling that maybe latex is gonna *cost* me! ouch!

…

additions: [26] is a critical yet hilarious review of Liptons book. [27] is an excellent, comprehensive review of the P vs NP problem which includes the early Godel and Nash angles by Johnson of Garey & Johnson fame. [28] is Chow’s recent work on “almost natural proofs”, a new angle that might supersede Natural Proofs.

1 thought on “math monster”

  1. Pingback: the joy of (cyber) mathematics | Turing Machine

Leave a comment