Proof of work is the competition encouraged by miners to find the correct hash.
The chance of finding the solution is so low that the when one is actually found this is considered proof that the miner has done the work and so deserves the block reward.
The problem is that this is very energy intensive and has grown more so as the Bitcoin network has expanded and peta hashes of power have been directed at solving the hash rather than gighashes.
The other result of this is that to stand a chance of actually mining the reward you need to buy some very large pieces of equipment which can cost at the top end $10,000 dollars. This has meant Companies backed by investors are gradually taking a large market share of the network hashing power.
To some people this has meant Bitcoin has lost some of its distributed charm, as its no longer run by individuals throughout the world on their personal computers. This is where Litecoin and Scrypt coins came to the fore where it was thought that there was no possibility of allowing large mining corporations to usurp network power.
There have also been further advances on Proof of work where innovative crypto currencies have introduced other forms of proofs, such as proof of stake and proof of burn.