The Complexity of Agreement