An NP-Complete Problem, Hands On

The Prompt

Select an NP-complete problem — Boolean satisfiability, graph colouring, the travelling salesman, subset sum, or another of your choosing — and solve a non-trivial instance by hand, without algorithmic assistance. Choose an instance large enough that brute force is uncomfortable but small enough that you can finish. Record the instance, the time spent, the strategy you adopted, and the moment at which the difficulty became palpable.

Completion Criteria

The problem chosen, the instance (specified or drawn), the solution, the time spent, and a brief account of the strategy used and where difficulty was felt.

Students who have attested

No Students have attested this quest yet. Be the first.