  We consider transmission over a general memoryless channel, with bounded
decoding complexity per bit under message passing decoding. We show that the
achievable rate is bounded below capacity if there is a finite success in the
decoding in a specified number of operations per bit at the decoder for some
codes on graphs. These codes include LDPC and LDGM codes. Good performance with
low decoding complexity suggests strong local structures in the graphs of these
codes, which are detrimental to the code rate asymptotically. The proof method
leads to an interesting necessary condition on the code structures which could
achieve capacity with bounded decoding complexity. We also show that if a code
sequence achieves a rate epsilon close to the channel capacity, the decoding
complexity scales at least as O(log(1/epsilon).
