Crowdsourcing NP-Complete Problems

I'm shifting gears and have decided to start pushing ideas out as web sites rather than technical prototypes. The reason for the gear change, is because I want users and I want to try broader experiments. I've got some ideas regarding drive-by (casual) contributions and patterns of collective intelligence I want to try out that require lots of varied user behaviour. Specifically, I intend on building a webapp that captures casual contributions made by users towards playing a game or solving a simple puzzle, the aggregation of which will contribute toward solving an NP-complete problem.

My intention is to capture my progress, thoughts, and problems on this blog while realising this modest project. After deciding to commit to the idea, I spent today mocking some screens, coding a proof of concept prototype for the Travelling Salesman Problem (TSP), and setting up a development environment.

The Application
The early vision for the site focuses on the user contributions as a game or puzzle, and the aggregation of all contributions received to date as a holistic solution. User contributions may be made anonymously, although signing-up permits the capture of user statistics, puzzle scores, and a leader board. The minimal interface focuses on the puzzle solving aspect, although provides some visualisation of the state of the holistic solution such as number of contributions, users, and holistic scoring. The holistic solution may be visualised, along with a graph of community performance over time. Problems would rotate after converge (lack of improvement) or a time limit, and a past-solutions repository will be accessible with solution visualisation. Tomorrow I want to find some free software to capture screen mock-ups or just hack out the templates.

The Problem
I chose the TSP first because I have worked with the general problem a lot in the past. Specifically with regard to a multiple user interaction model across a P2P network (see IIDLE), and with regard to a stardardised problem solving framework (see my OAT project). Simple symmetric Euclidean TSP's can be addressed by the aggregation of multiple sub-graph solutions. The sub-problems or "puzzle" to be addressed by users will be to connect a set of points to form a sub-tour (connect the dots). My assumption is that the human pattern recognition will be at least as good as a Greedy Nearest Neighbour (NN) solution, and hopefully with tweaking of the interface and aggregation function, better than NN. My technical prototype verified that the greedy aggregation of multiple sub-tours demonstrates that a NN-like solution can be achieved easily as long as enough contributions are received. I need to formalise notions of "enough" and "convergence" for problem rotation.

The Technology
I have decided to build the application using Ruby on Rails, based on my previous assessment of the technology landscape. I have played around with rails before in late 2006 on my mac, although that was some time ago, and I'm developing this site on a PC (for now). I hit the rails site, got running with InstantRails and RadRails using Aptana. I then did a read a quick refresher with the ONLamp articles "rolling with rails revised" (parts one and two). The tools seem nice and work together well. At this stage it feels like the old PHP and Tomcat/Struts days.

I only had the notion for the project at lunch time, so it's all still fresh and new. I expect to bash out some page and database templates tomorrow and think through the user experience. I'm going to try and put-off getting into the technical aspects of problem definition/integration/visualisation for as long as I can because that's the fun stuff and I want to get on top of the mundane (user-centric) things first.