For PoW, the important property seems to be that there's no shortcut to doing the hard work e.g. I could ask you to sum all the numbers from 1 to N for a very high number of N to prove you've done some work, but the flaw there is that a shortcut exists where where you only have to calculate (n(n+1))/2 to get the final answer in a fraction of the time.

> significant amount of complexity is very much needful

I think you're using the word complexity in a different way to the way I was using it. I'm guessing you probably mean "is difficult to calculate the result without taking a shortcut" and not "is conceptually simple to understand and analyse for flaws by a human". Ideally, you want both to be true but that won't be the case for all PoW processes.