Congestion control lies at the heart of the general problem of traffic management in asynchronous transfer mode (ATM) networks. The primary function of congestion control is to ensure good throughput/delay trade-off performance. This paper presents a fundamental study on the performance limits of one-bit protocols for congestion control - implemented by many ATM switch vendors because of its low hardware requirements - using a new complexity theoretic framework. We derive the first known tight bounds on the buffer size required for one-bit protocols that fully utilize link capacity and guarantee no cell loss under network congestion. In particular, we show that any such one-bit protocol will result in cN^2 + O(dN), where N is the number of greedy sources in the network, d is the link delay, and the constant c is a parameter of the specific protocol.