Deceptively simple

I have heard people use the phrase "deceptively simple" in situations that seem to have opposite meanings. Is it supposed to refer to something that is more complex than it appears on the surface, or something that appears complex but is actually simple?

I have understood it to mean simple on the surface but actually quite complex. But I just asked a passer-by and he thought the opposite.