We describe COMPLEXITY COIN, a digital currency which is backed by the high-frequency solving of difficult, useful computational problems. COMPLEXITY COIN achieves many of its goals via mechanisms which are abstractly-similar to BITCOIN, but which differ in that the "heat backing" is being applied to problems which are COMPLETE in various specific complexity classes (NP, #P, co-NP, etc). The problems which get solved are sourced from a mixture of random sources (similar to BITCOIN) and non-random sources (individuals who are willing to put up bounties on getting their problems solved). Datasets for these problems are shared via BitTorrent. The currency rewards miners for collaborating with others to solve problems quickly, which creates an incentive for miners to seed the datasets. Further, the currency includes a degenerate case where-in it is practical to pay miners for their contributions as seeders, and this degenerate case occurs as an emergent, natural property of the system. Lastly, COMPLEXITY COIN is better than Bitcoin because it's not-yet too-late to get-in on it and make a digital fortune by paying higher energy bills.