Science: Where computers prove incapable - Fermat's Last Theorem has been cracked, but Darrel Ince explains how researchers have shown that some problems cannot be solved

Earlier this year, the news came through that Professor Andrew Wiles of Princeton University had succeeded in proving Fermat's Last Theorem - a puzzle that had lain unresolved for three centuries.

Proving mathematical statements to be true (or false) is one of the activities mathematicians indulge in most frequently. Two features of the process often surprise the layman. First, how error-prone the business of proving things is. There are plenty of cases of a seemingly straightforward proof being published, only for it to be modified or even proved false a few months later. The second surprising fact about proofs is that they can be very long. The proof of Fermat's theorem should, in full, occupy hundreds of pages of text.

Now research scientists at the University of California, Stanford University and AT & T laboratories have startled the mathematical world by developing a technique capable of proving - or at least certificating - the correctness of a proof. Of obvious importance to mathematicians, this also has major ramifications for computer scientists.

In effect, the researchers have devised the mathematical version of ultrasonic testing, which highlights any flaws in a proof. A series of operations - transformations - are applied to the text of a proof and any errors become more visible.

There are two implications for computer scientists. The first concerns 'formal methods of software development'. This is the generic term used to describe methods that use mathematics both to draw up the specifications for what a piece of software should achieve and to design the software systems themselves to meet the specifications. Such methods are normally used to develop programs for ultra-reliable applications such as the control of nuclear power stations.

A major problem that has dogged this area is that the proof process is long and error-prone. One incorrect step could lead to a serious error - which could result in loss of life. Use of formal methods has been confined largely to projects where the economic loss due to an error would be so great as to justify employing large numbers of highly trained staff to develop the mathematical specifications and then to check the design and the proofs of the code. The new techniques for the certification of proofs promise to reduce substantially the amount of checking and validation needed.

The second effect of the research concerns a class of computer applications known as NP (non-polynomial)-complete problems. The time taken for a program to solve such a problem increases dramatically depending on its complexity, to the point where it would take longer than the life expectancy of the universe. These are not abstract academic problems, but occur, for example, in the design of telecommunications systems or the layout of computer circuits on silicon chips.

Until recently researchers have believed that although an exact solution to these NP-complete problems has not been possible, approximate ones can be found. An archetypal NP-complete problem might involve devising a layout of roads to connect all the cities in an area using the smallest amount of road material. Computer scientists believed that while an optimal solution would never be possible, there could be approximate solutions that came within 99 per cent of the minimum amount of material.

The research in the US has proved that such programs do not exist for large classes of NP-complete problems - and that such problems will almost certainly be incapable of being computerised. This spin-off alone is being claimed as the major computer science discovery of the past two decades.

The writer is professor of computer science at the Open University.

Neil Warnock
football'New' manager for Crystal Palace
peopleGerman paper published pictures of 18-month-old daughter
Arts and Entertainment
'A voice untroubled by time': Kate Bush
musicKate Bush set to re-enter album charts after first conerts in 35 years
Angel Di Maria poses with Louis van Gaal after signing for Manchester United
Arts and Entertainment
BBC series 'Sherlock' scooped a hat-trick of awards on the night. Benedict Cumberbatch received the award for Actor, Miniseries or Movie ('Sherlock: His Last Vow') while Martin Freeman won the award for Supporting Actor, Miniseries or Movie. Neither actor was present to collect their awards
Life and Style
ebooksAn evocation of the conflict through the eyes of those who lived through it
Travel Shop
the manor
Up to 70% off luxury travel
on city breaks Find out more
Up to 70% off luxury travel
on chic beach resorts Find out more
sardina foodie
Up to 70% off luxury travel
on country retreats Find out more
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
Independent Dating

By clicking 'Search' you
are agreeing to our
Terms of Use.

iJobs Job Widget
iJobs General

Oracle DBA (Database Administrator, 10g, 11g, PL/SQL)

£45000 - £50000 Per Annum + £5k shift allowance, 12% bonus, benefits: Clearwat...

Cover Supervisor

£45 - £65 per day: Randstad Education Chester: Job Opportunities for Cover Sup...

IT Teacher September strt with view to permanent post

£110 - £130 per day + Competitive rates of pay: Randstad Education Reading: IT...

Qualified Nursery Nurse

Negotiable: Randstad Education Crawley: This independent Nursery is looking fo...

Day In a Page

Kate Bush, Hammersmith Apollo music review: A preamble, then a coup de théâtre - and suddenly the long wait felt worth it

Kate Bush shows a voice untroubled by time

A preamble, then a coup de théâtre - and suddenly the long wait felt worth it
Robot sheepdog technology could be used to save people from burning buildings

The science of herding is cracked

Mathematical model would allow robots to be programmed to control crowds and save people from burning buildings
Tyrant: Is the world ready for a Middle Eastern 'Dallas'?

This tyrant doesn’t rule

It’s billed as a Middle Eastern ‘Dallas’, so why does Fox’s new drama have a white British star?
Rachael Lander interview: From strung out to playing strings

From strung out to playing strings

Award-winning cellist Rachael Lander’s career was almost destroyed by the alcohol she drank to fight stage fright. Now she’s playing with Elbow and Ellie Goulding
The science of saturated fat: A big fat surprise about nutrition?

A big fat surprise about nutrition?

The science linking saturated fats to heart disease and other health issues has never been sound. Nina Teicholz looks at how governments started advising incorrectly on diets
Emmys 2014 review: Can they genuinely compete with the Oscars

Can they genuinely compete with the Oscars?

The recent Emmy Awards are certainly glamorous, but they can't beat their movie cousins
On the road to nowhere: A Routemaster trip to remember

On the road to nowhere

A Routemaster trip to remember
Hotel India: Mumbai's Taj Mahal Palace leaves its darker days behind

Hotel India

Mumbai's Taj Mahal Palace leaves its darker days behind
10 best pencil cases

Back to school: 10 best pencil cases

Whether it’s their first day at school, uni or a new project, treat the student in your life to some smart stationery
Arsenal vs Besiktas Champions League qualifier: Gunners know battle with Turks is a season-defining fixture

Arsenal know battle with Besiktas is a season-defining fixture

Arsene Wenger admits his below-strength side will have to improve on last week’s show to pass tough test
Pete Jenson: Athletic Bilbao’s locals-only transfer policy shows success does not need to be bought

Pete Jenson: A Different League

Athletic Bilbao’s locals-only transfer policy shows success does not need to be bought
This guitar riff has been voted greatest of all time

The Greatest Guitar Riff of all time

Whole Lotta Votes from Radio 2 listeners
Britain’s superstar ballerina

Britain’s superstar ballerina

Alicia Markova danced... every night of the week and twice on Saturdays
Berlin's Furrie invasion

Berlin's Furrie invasion

2000 fans attended Eurofeurence
‘It was a tidal wave of terror’

‘It was a tidal wave of terror’

Driven to the edge by postpartum psychosis