Do NOT use this idea to prove P != NP

First off, let me just say that unlike the last couple of posts, today's entry actually is about P vs. NP.

A blog I've been reading lately is Logicomp by Anthony Widjaja To, which explores the connections between logic and computational complexity. There are a couple of things about his blog I really like. The first is, Anthony is using the blog to present an ongoing tutorial on finite model theory and descriptive complexity, which are a couple of topics I hope to learn more about. The second thing is, Anthony periodically talks about my favorite subject, P vs. NP and possible approaches to a proof, for example here and here.

I've noticed a number of items relating to P vs. NP in the blogosphere lately. For example, via David Molnar comes this announcement of a workshop on P vs. NP at Berkely. This is wild-sounding stuff -- group theory and categories and spectral calculations. I'm a little skeptical about an algebraic approach to P vs. NP, but this sounds pretty serious.

On the opposite side of P, back on Anthony's blog is this entry about a possible proof by Michael Taitslin that NL != P. While this not a proof of P vs. NP, being able to decide whether any of the containments

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP

are proper is bound to bring one fame (even if only one of these will also bring fortune).

All this has inspired me to propose my own suggestion for an approach to proving P!=NP. Now it seems to me that proof ideas can be grouped into three general categories:

1. Ridiculous - the kind where you have a brilliant flash of insight, but you look at your notes the next day and wonder what the heck you were thinking. Hopefully you have this realization before mentioning your idea to too many people. Ideas from this category seem to abound on Usenet.


2. Conventional - a general idea for an approach to the problem, but without any concrete details. It might, with years of research, develop into an actual proof. Or not. For example, any variation on "look for a non-relativizing diagonalization" or "look for an 'unnatural' circuit lower bound proof technique". Googling on an idea in this category, you might find a cluster of articles from 10 years ago, but nothing more recent because nobody could figure out where to go with it.


3. Inspired - you have a concrete idea for an actual proof with no obvious roadblocks to implementing it. Obviously, you don't tell anyone about ideas in this category! If anyone asks what you've been up to, tell them something from category 1 to throw them off the track.

Okay then, now for a proof idea. Let's see... For those of you who have followed this blog from the beginning, I did remember my proof idea from that night, and I promptly wrote it down on a piece of paper which is somewhere here in the house, I'm sure... Oh well, here is a different proof idea. You can draw your own conclusions about which category it belongs in...

Define a k-head pushdown automaton (k-PDA) to be a deterministic pushdown automaton with the usual push-down storage, but with k read-only two-way input heads (the input has delimiters on either end that the heads cannot move past). Then

P ≡ the class of languages recognizable by a k-PDA for some k.

Proving this statement appears as a problem in Sipser's text. I think the original source is this paper by Stephen Cook [1].

The thing that fascinates me about this result is that it gives a characterization of P with no explicit time bound. Cook compares several different machine models in his paper, and suggests that the simpicity of the models may aid in identifying hard problems that lie outside of P (although his terminology is different, as this paper precedes the development of the current nomenclature for P, NP, etc.). There were a number of papers which followed Cook's, and then the subject seemed to dry up. That might be changing, though, as I did notice at least one recent paper [2].

There is one thing which is glaringly absent from all these papers, however. There is not any equivalent characterization for NP. The class NP is covered in the papers that followed Cook's, but always in a machine model that included an explicit time bound. So here is my modest suggestion: find a machine model for NP without an explicit time bound, similar to a k-PDA. This would allow an apples-to-apples comparison of simple machine models for P and NP, which presumably would help explicate any differences between the classes. After all, how hard could this be? :-)

If no one beats me to it, I'll spend some time in the future on this blog trying to find such a model (maybe when I re-study the relevant sections in Sipser). On the other hand, if reading this helps inspire you to prove P!=NP, please mention this blog in your acknowledgements!


[1] Cook, S. A. 1971. Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. J. ACM 18, 1 (Jan. 1971), 4-18.

[2] Holzer, M. and McKenzie, P. 2003. Alternating and empty alternating auxiliary stack automata. Theor. Comput. Sci. 299, 1-3 (Apr. 2003), 307-326.

Miscellany

Blogger has finally implemented a backtracking feature (now if only they'll add categories, I can be content), and I've replaced the Technorati trackback link at the bottom of each post with a Blogger 'backlink'. Just in time, as it turns out, for my last post to actually get linked to. Thanks Suresh and Anthony. Of course, you guys realize that my post was not about P vs. NP proofs. I have a real affection for these, flawed or otherwise. The hypercomputationalists are another matter; I may have more to say about them in the future. I'm still mulling over a few things (sorry, I think slowly). In the meantime, here are a few miscellaneous thoughts I need to unload because they're clogging up the works...

Elsevier:

In the comments to my last post, Chris Leonard at Elsevier responds to a remark I made about the journal Theoretical Computer Science. Not being a part of academia, and never having published a research article, I am not familiar with the issues surrounding scientific publishing. But Chris seems to be genuinely interested in receiving feedback from people in the field, so I would encourage you to take advantage of that and send your suggestions or gripes to him. And although I absolutely do NOT recommend it, I can't help mentioning that if you are feeling angry and at a loss for words, you might want to check out this article first (thanks to Bora Zivkovic). (Seriously, though, I'm only joking. Please be polite.)

Cosma's notebooks:

I was trying to find an online copy of an old Claude Shannon article, and in the process came across these notebooks of Cosma Shalizi's. Now evidently Cosma is well known in these parts, at least to people who have been around longer than I have. All I can say is, as someone who loves books and thought he had a nice little collection, I feel so, so inadequate now.

Backlash against editor who published ID:

This story, Intelligent Design and Academic Freedom was on NPR's All Things Considered program two days ago. I haven't noticed any feedback yet about this on the Web, and I'm curious about people's reaction to it. Are academics really this petty and vindictive?

ASCIIMathML and Blogger

Finally, here is a little technical issue I noticed with the new backlink feature: The Blogger backlink display can be garbled by ASCIIMathML. The Blogger template uses variable tags like <$BlogBacklinkTitle$>. Most of these get resolved on the server side, so your browser (and ASCIIMathML) never see them. But the backlinks get resolved on the browser, and evidently ASCIIMathML gets to them before the Blogger script does. So <$BlogBacklinkTitle$> can turn into something like <BlogBackl∈ktit≤>.

According to ASCIIMathML's creator, Peter Jipsen, the easiest workaround is to just remove the dollar sign as a potential delimiter and use the backquote instead. To make this change in the script, find the line near the top of the file that looks like so:

var AMdelimiter2 = "$", AMescape2 = "\\\\\\$", AMdelimiter2regexp = "\\$";

and change the delimiter sequences to something that will never appear in the page, such as the following:

var AMdelimiter2 = "NeverInText", AMescape2 = "NeverInText", AMdelimiter2regexp = "NeverInText";

Happy coding!