I think almost anyone who has studied protein 3D structures would agree that it is a hard problem.
For the uninitiated, proteins are made out of chains of amino acids. Each amino-acid consists of a backbone and side-chains. The properties of the side-chains determine the structure that the chain will take on in 3D. For example, polar side-chains may repell each other, and hence tend not to be close. Another example is hydrophobic ("water-fearing") side-chains which need to be on the inside of the protein, away from the water molecules that surround a protein inside the cell.
There's more than one way to determine protein 3D structure. You can take the actual protein, crystallise it, shoot x-rays at it and work out the structure from seeing how the x-rays diverge. Or you can take all of the contraints mentioned above, encode them in a computational model and get a computer to crunch the numbers for you until it finds the optimal structure.
Or, well, you could just get people to do it by hand. For free. And have fun while they're doing it.
That's the principle behind FoldIt, a new game based on, yes, you guessed it, protein structures. The idea is that protein folding is much like a puzzle, and people love doing puzzles. So we let them fold virtual proteins, and evaluate the structures based on the constraints that we know about. Add some fun sounds when you're tugging and dragging proteins, a bonus for reducing the number of moves starting from the initial configuration, and an element of competitiveness in the form of an online ladder, and you've got a fun little game that people will actually want to play.
FoldIt is currently in open Beta and completely free to play. I've tried it out, and it really is a lot of fun. The online option allows you to chat with fellow folders while you're playing, and the interface is simple and intuitive. You don't even have to know anything about proteins; there's a very easy tutorial to get you up to speed, and you'll figure out soon enough what works and what doesn't.
It will be interesting to see if FoldIt players can come up with better protein foldings than a computer could. FoldIt is not the first instance of a "useful" game I've come across. I first heard about the concept, called human computation, in the context of a game called ESP that gets its users to label images with text. It makes you wonder what other arduous bioinformatics tasks we could turn into games (gene-finding anyone?).