Firstly - Perplexity is not a commonly used word. I had to look it up to find out what it means, and even that it is a real word. Complexity is related to a thing. A bus system can be very complex. English grammar is very complex. Perplexity is related to a person's state. Typically, people will get perplexed by complex things. "His perplexity is partly due to the complexity of the puzzle, but more to the fact that he is drunk."

Complexity or things which are "complex" are those things which require different understandings. For example, there is no "simple" way to explain the operation of a computer. A Computer is very complex and its explanations are "complicated. Perplexity (noun) and Perplexed (verb) have to do with confusion about something we try to understand. If a person is confused, they are in a state of "perplexity". Perplexity has to do with the state of being confused about a subject. For example, we may be "perplexed" about word meanings. That happens when we are in a state of being "perplexed". An explanation about a word meaning, can be "complex". For example, if I begin explaining to you the difference between PERCEPTION and CONCEPTION, you will be studying COMPLEX differences, that might not be easy for you to understand. For the moment, a simple explanation for you is perhaps best. Think of "perplexity" as the same as confusion, and think of "complexity" as the condition of a subject that is difficult to understand or explain.

Also, to add to Gary's: to be perplexed is to be confounded, bewildered.