Dimitri Scheftelowitsch
  • Member for 11 years, 2 months
  • Last seen more than 10 years ago
Hardness jumps in computational complexity?
Accepted answer
48 votes

One of the more interesting applied examples of hardness jumps can be observed in the following problem: Consider a soccer league championship with $n$ teams: The problem of deciding whether a given ...

View answer
Algorithms from the Book.
8 votes

I wonder nobody mentioned Schöning's random-walk algorithm for 3-SAT solving yet. It it very simple: Start with a random assignment As long as there exists an unsatisfied clause: Flip a randomly-...

View answer