Free seminar: Maths problems that are too hard for your computer29 September 2004
Visiting Lecturer, Dr Ron Monson from the University of Western Australia, will present a free seminar on the celebrated P-NP conjecture, what it is, how it places limits on a computer’s power and what it has to do with mathematical thresholds. Dr Monson’s visit is sponsored by Charles Darwin University’s School of Engineering, School of Information Technology and the University Maths Club Aristotle once held that fossils were the remnants of life's botched attempts to spontaneously generate from mud. He also developed a logical system that was a forerunner to what we now call Propositional Logic. While it took some 2000 years for the former idea to itself become fossilized, (using a contribution from this university's eponym), his latter one has developed into one of the foremost open questions in mathematics and computer science, namely - is P=NP? Equivalently, given any arbitrary propositional formula f, can you always solve f=1 in a "reasonable" amount of time. The smart money says you can't (and hence PNP) while a lot of money (A Clay Million) says you won't be able to prove that you can't. The reason we are so interested in solving f=1 efficiently is that it turns out that a host of problems in an amazingly diverse range of fields can be quickly transformed into formulae of this form. Through experiments investigating this in the early 1990's, it was observed that as you increase the size of large, random formulae f of a set structure, the probability of a solution existing for the corresponding equation f=1, decreases very slowly until all of a sudden, it dramatically drops to almost 0. In this talk we present recent research that for the first time describes this "phase transition" algebraically rather than experimentally. That is, we demonstrate a mathematical formula whose graph illustrates this transition and discuss the possible implications this has for the efficient solving of formulae like f=1. A BBQ will follow the one hour presentation. Cost of BBQ lunch is $5.00 for non members. Maths Club Membership cost for Semester 2 is $5.00 and registration is available on the day.
|
