How hard can it be? (An optimistic brush with computational complexity theory)

Professor Vic Grout

Director of the Centre for Applied Internet Research (CAIR)
Glyndwr University, Wrexham, Wales

Summary

Computers can do anything, right? OK, maybe not the early ones but the ones we have today are thousands and thousands times more powerful so they can, surely? Or, even if not now, the machines of the future will be millions and millions of times better so eventually we’ll get there, won’t we? Computers don’t have any real limits, do they?

Well, it may not be as simple as that! It turns out there are different types of ‘problem’ in computing terms. Yes, some are easy enough and we’ve dealt with them already; but others get more complex as they get bigger and we haven’t cracked them yet – although we might soon; whereas some prove more difficult in the long term and some we actually know really can’t be solved at all!

This talk uses a number of simple, and easy to grasp, examples to discuss the various levels of complexity and intractability to be found in computational problem-solving. We look at the distinguishing features of easy and hard problems and note how one can often masquerade as the other. Nothing is quite as straightforward as it seems and, at the heart of it all, is an unanswered question that has kept mathematicians and computer scientists busy for a long time now – for which there is a million dollars on offer to the eventual solver!