Open Problems

One topic that comes up on a regular basis is the question of how to come up with open problems that might be suitable for tackling. Of course everyone knows about P vs. NP, and like Fermat's Last Theorem in number theory, this problem can serve as motivation for studying the foundations of computational complexity. However, as was the case with FLT, it is not a problem that a student would hope to make any real progress against. One difficulty with identifying problems that are hard enough to be interesting, but not so hard as to be hopeless, is that the people who are familiar with such problems might be reluctant to advertise them--they understandably might want to tackle the problems themselves first, or in the case of faculty, to give the problems to their students to work on.

So it was especially nice to learn (via David Eppstein) about the Open Problem Garden created by Matt DeVos and Robert Šámal. The Garden is a wiki-style repository of open problems from math and computer science, so anyone can register and contribute their own entries. Problems are categorized by subject (graph theory, combinatorics, etc.), and rated according to importance. Problems are not rated for difficulty per se, but there is a yes/no indicator for whether the problem might be suitable for an undergraduate student. It looks like the database was preloaded with the problems from Bojan Mohar's Problem of the month page, so it is currently heavily weighted toward graph theory. I'm really hoping that as time goes on, people in the TCS community will use this repository to store their own open problems.

There is as of this writing a single entry in the TCS subject category: Subset-sums equality. This search variant on the NP-complete decision problem SUBSET-SUM is one which I haven't seen before. Unfortunately, the entry does not currently contain much background or any references, so perhaps if someone reading this is in the know, they could flesh out the entry a bit. (A quick search turns up this article on finding approximate solutions to the problem.)

While I'm searching around, perhaps I should look for other sources of open problems... Unfortunately, a lot of the hits returned by Google are pages describing P vs. NP and not much more (including, surprisingly, this Wikipedia article). Open problems have been discussed on at least a couple of occasions on the Computational Complexity blog, here and here. In fact, in the comments to that second post, Matt DeVos puts in a plug for the Open Problem Garden (which was in beta at the time). That was back in March, and evidently no one in the meantime has been sufficiently motivated to add any additional TCS open problems. Pity, that.

Finally, for something of a slightly different flavor, here is David Johnson's Challenges for Theoretical Computer Science. Instead of a list of conjectures to be proven, this is a list of broad challenges for computer science, perhaps reminiscent of David Hilbert's list of problems for mathematics.

Academic Haiku

Jim Gibbon is holding a contest to see who can best describe a piece of academic research in the form of a haiku. You'll need to hurry though, because the deadline for submission is the 21st. (Hat tip to OmniBrain.)

My own submission is as follows:

There exist problems
intractable to decide
yet easy to check

For those of you who don't immediately recognize what that's describing, let's say it's for a yet-to-be-written paper entitled, "On an open problem of Cook".

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.

Spooky science

Hi again,

It's been a little longer than I would like since my last post, but we've been taking turns getting sick in my family and it's slowed me down a bit. Well, this is wishful thinking but maybe it will help build up my immune system for the upcoming outbreak of avian flu.

Since this is Halloween, I thought I'd post about something befitting the occasion, computer science's own version of the occult. Or, since discussions of the differences between ID and science are quite popular on the blogosphere now, maybe we should refer to this as our own version of intelligent design. But first...

One of my favorite recreational pages on the Web is Gerhard Woeginger's P vs. NP Page. Not surprisingly, a lot of the entries on this page would appear to be the work of crackpots. However, many others of these were (seemingly) serious attempts at a proof by academics. Perhaps the most illustrious P vs. NP author appearing on this page is Selmer Bringsjord, who is chair of the department of cognitive science at Rensselaer Polytechnic Institute.

I can recall seeing much discussion on Usenet and the blogosphere when his paper An Argument for P=NP, co-authored with Joshua Taylor, first appeared last year. A lot of the commentary was of the sort that the paper obviously was a parody, since it's inconceivable that Bringsjord would actually believe his own ridiculous line of reasoning. It also spawned some investigations into the premises of Bringsjord's arguments, the best example of which in contained within this article by Scott Aaronson.

I noticed recently that Bringsjord has updated his paper, to respond to some of the feedback it generated. So if it was intended as a joke, it must be of the "long-running" variety. The thing I find most curious about the whole episode, though, is not within the P=NP paper itself. On Bringsjord's home page, just below a link to the P=NP paper, is a link to the paper The modal argument for hypercomputing minds. In it, Bringsford argues that, er, well, let me just quote from the abstract:

... we give herein a novel, formal modal argument showing that since it's mathematically possible that human minds are hypercomputers, such minds are in fact hypercomputers. We take considerable pains to anticipate and rebut objections to this argument.

The thing is, the format of this paper, which takes a questionable premise and then uses formal reasoning via modal logic to reach a "remarkable" conclusion, is very similar to the P=NP paper. The conclusion I am tempted to come to is that Bringsjord, in his P=NP paper, is parodying his own work.

What then, should we make of the hypercomputation paper? This paper is published in no less than Elsevier's Theoretical Computer Science, Volume 317 (June 2004), pages 167-190. This is part of a special issue devoted to "super-recursive algorithms and hypercomputation". A glance through the table of contents lists a slew of articles with similar subject matter. Has Theoretical Computer Science gone all soft and fuzzy? Perhaps Chris Leonard, if he reads this, would care to comment.

Many of the authors are members of the Hypercomputation Research Network, which seems to be some sort of cabal of sorcerers community of philosophers intent on plumbing the depths of the mind. Certainly nothing wrong with that; I find the philosophy of mind to be a fascinating subject. But perusing several of the articles linked to on this site, I find the level of reasoning to be painfully similar to what Bringsjord uses in his papers.

So what do you think? Do the hypercomputationalists escape scrutiny because they are philosophers and not scientists, and therefore not held to any the same standards? Or are they theoretical computer science's equivalent of alchemists?

Welcome

Last night I figured out how to prove that P != NP. Well, okay, not exactly. I didn't have a "Ureka!" moment where I suddenly understood what technique to use to show P != NP. What did occur to me was a general approach that, with a lot of time and effort, might conceivably lead to a proof. This was while I was lying in bed near to being asleep, which is when a lot of my ideas seem to come to me. My first thought was that I ought to get up out of bed and write down the idea, so I could explore it some more in the morning. Maybe do a Google search and see if anyone else had already published anything related. However, I was awfully tired at the time, and the bed was awfully comfy. Also, my late-night brainstorms have a history of looking nonsensical in the light of day. While I was debating the matter with myself, I fell asleep.

As you have no doubt already guessed, I do not remember what the idea was. Perhaps I'll remember it at some point. More likely, I'll think it up again one day in the future, but won't realize that it's the same brainstorm I had last night. My fear is that this cycle will keep repeating itself, and like the protagonist in the movie Memento I'll be doomed to rediscover the idea over and over without ever being able to remember it. From now on I'm keeping a pad and pen on the nightstand, and writing everything down no matter how silly or insignificant it might seem.