Correction, Bitcoin mining is NP-hard or at least I suspect it is. I believe there is no proof that it is so it's a suspicion based on the fact that Bitcoin mining wouldn't work if it wasn't. The only way to solve consensus problems based on my current understanding is with soft computing techniques such as Nakamoto consensus or weighted stake holder Proof of Stake or ant colony type algorithms such as with Maidsafe. In any case the solutions involve fuzzy logic where the yes or no is based on the percentage of votes or amount of hash or 51% etc.