I heard that the complexity of proof of work in blockchain can vary. On what factors does it depend? Is it possible that that proof of work i.e. the required hash starting with certain number of zeros can't be found? What happens then? Do the transaction wait in the queue until the hash is found
Generally speaking, the difficulty is increased if the “mean time between two succesful mined block” diminishes. It is a so called “closed loop” control system. As a result, the time between two blocks tends to remain stable. The solution having a certain number of zeros is not guaranteed existing, but any solution lower than it is ok for the system, and is accepted, so definitely it exists a set “lower than” where a suitable solution can be found.