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.