What is Complexity?

Sometimes, we hear people talking about how complex or difficult is for a machine to solve a problem, or to perform certain tasks that, in humans, involve thinking. But what is exactly the complexity of a problem? Humans compare and evaluate problems and situations all the time, for example, between two situations s1 and s2, we can say a situation s1 is more complex than s2, because we may have some information about these problems. But, is it possible to define the complexity in terms a machine could understand?, and if possible, how can we measure how complex can a problem be? Perhaps, most of you have already heard of the big O notation.