You’re deep in the Congo. You’ve got an iPhone with some charge left, but there’s no cell tower for hundreds of miles. With life-or-death urgency, you need to know the definition of the complexity class SBP and its relationship to BPPpath. What do you do?
Not to worry: Satoshi Hada has created a free Complexity Zoo app for the iPad and iPhone. I tried it out and it works great!
You get a cold call from yet another solitary genius who’s discovered a simple linear-time 3SAT algorithm. You tell him to implement the algorithm and test it out, and then you’ll talk. Half an hour later, he tells you he’s done so and it works perfectly. So you tell him to go factor the 617-digit RSA challenge number. But being an iconoclastic genius, he never learned how to reduce factoring to 3SAT. What do you do?
Relax: answering challenge #2 from this blog post even before the post went up, USC students Henry Yuen and Joe Bebel have created a great web application called ToughSAT, which generates hard SAT instances on demand, based on factoring, subset sum, or even a “hard problem cocktail.” As a commenter helpfully alerted us, a few years ago Paul Purdom and Amr Sabry of Indiana University already created a similar site that generates hard SAT instances based on factoring.