Tea Leaves

Selected Problems in Computability

Sometimes, we do hardcore research in computer science. It's in our blood. Here are some of the papers we have submitted to various academic journals at the moment.

10. The Travelling Salsman problem (peterb)

9. Mutual Exclusion in the Men's Room (psu)

8. "Given a description of a program and a finite input, decide whether the program is a lousy piece of fucking garbage." Also known as the Hating problem. (peterb)

7. Compute the value of pie to an arbitrary number of diners. (peterb)

6. Finding an assignment of substitute teachers that makes any 3 variable logical formulae true, also known as 3SUB (psu)

5. For any non-trivial property of partial functions, the question of whether a given algorithm computes a partial function with this property is irritating. (peterb)

4. The Unstable Marriage problem (psu)

3. Redundant Array of Idiot Developers (peterb, with props to sdavis for the assist)

2. All Cretans are liars. No, seriously. Have you ever been to Crete? I mean, Jesus. (peterb)

1. Automatic Path planning in hostile environments: the Blood Gulch case study (psu)

0. The Speculative Dining Philosopher's Problem: Eat dessert first. (psu)