Computer Science problems that are still problematic

Graph isomorphism.

Basically, most naturally occuring problems are either easy (P) or probably hard (NP). There were, if memory serves, 2 or 3 problems that fell "in-between". Primality was one, but that was recently proven to be in P. Graph Isomorphism is th eother.

Graph isomorphism is this question: Given G1 and G2, is G2 simply G1, but "relabelled"? Equivelantly, can we relabel G2 so that it is the exact same as G1?

Wiki articles! A general overview, and the article concerning the issue of its complexity class here.

Edit: I really have to remember to type ALL the words.

ORM is the Vietnam of Computer Science -Ted Neward

Which is to say, it isn't solved to many peoples satisfaction.

Note that the Church-Turing thesis is not actually, really a statement about mathematics. It is a statement about the physical world.

The closest you can come to a proof of it is something like "it is true under the standard model".

This isn't to say it couldn't be formalized to a larger extent, but the best you can hope for is to clarify specific assumptions about the physical world.

P =? NC would be my vote. Automatic manycore parallelization would be possible under P = NC, but it's believed that the two are different and hence there are P-complete problems that are hard to parallelize. Understanding which problems fall into this class is increasingly important.