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.

PROMOTED VIDEO
Sport
Wembley Stadium
footballNews follows deal with Germany
Arts and Entertainment
A spell in the sun: Emma Stone and Colin Firth star in ‘Magic in the Moonlight’
filmReview: Magic In The Moonlight
Voices
voicesApple continually kill off smaller app developers, and that's no good for anyone
Sport
A 'Sir Alex Feguson' tattoo
football

Arts and Entertainment
Ben Whishaw is replacing Colin Firth as the voice of Paddington Bear
tv

Thriller is set in the secret world of British espionage

News
ebooksAn unforgettable anthology of contemporary reportage
Life and Style
life

News
ScienceGallery: Otherwise known as 'the best damn photos of space you'll see till 2015'
Life and Style
fashion

Bomber jacket worn by Mary Berry sells out within an hour

Life and Style
tech
Sport
Andros Townsend is challenged by Vladimir Volkov
football
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
Independent Dating
and  

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

iJobs Job Widget
iJobs General

Graduate BI Consultant (Business Intelligence) - London

£24000 - £30000 per annum + benefits: Ashdown Group: Graduate BI Consultant (B...

Service Delivery Manager (Product Manager, Test and Deployment)

£40000 - £55000 per annum: Ashdown Group: Service Delivery Manager (Product Ma...

English Teacher

£110 - £130 per day: Randstad Education Reading: English Teachers with QTS nee...

Maths Teacher

£110 - £130 per day: Randstad Education Reading: QTS Maths Teachers needed for...

Day In a Page

Mystery of the Ground Zero wedding photo

A shot in the dark

Mystery of the wedding photo from Ground Zero
His life, the universe and everything

His life, the universe and everything

New biography sheds light on comic genius of Douglas Adams
Save us from small screen superheroes

Save us from small screen superheroes

Shows like Agents of S.H.I.E.L.D are little more than marketing tools
Reach for the skies

Reach for the skies

From pools to football pitches, rooftop living is looking up
These are the 12 best hotel spas in the UK

12 best hotel spas in the UK

Some hotels go all out on facilities; others stand out for the sheer quality of treatments
These Iranian-controlled Shia militias used to specialise in killing American soldiers. Now they are fighting Isis, backed up by US airstrikes

Widespread fear of Isis is producing strange bedfellows

Iranian-controlled Shia militias that used to kill American soldiers are now fighting Isis, helped by US airstrikes
Topshop goes part Athena poster, part last spring Prada

Topshop goes part Athena poster, part last spring Prada

Shoppers don't come to Topshop for the unique
How to make a Lego masterpiece

How to make a Lego masterpiece

Toy breaks out of the nursery and heads for the gallery
Meet the ‘Endies’ – city dwellers who are too poor to have fun

Meet the ‘Endies’ – city dwellers who are too poor to have fun

Urbanites are cursed with an acronym pointing to Employed but No Disposable Income or Savings
Paisley’s decision to make peace with IRA enemies might remind the Arabs of Sadat

Ian Paisley’s decision to make peace with his IRA enemies

His Save Ulster from Sodomy campaign would surely have been supported by many a Sunni imam
'She was a singer, a superstar, an addict, but to me, her mother, she is simply Amy'

'She was a singer, a superstar, an addict, but to me, her mother, she is simply Amy'

Exclusive extract from Janis Winehouse's poignant new memoir
Is this the role to win Cumberbatch an Oscar?

Is this the role to win Cumberbatch an Oscar?

The Imitation Game, film review
England and Roy Hodgson take a joint step towards redemption in Basel

England and Hodgson take a joint step towards redemption

Welbeck double puts England on the road to Euro 2016
Relatives fight over Vivian Maier’s rare photos

Relatives fight over Vivian Maier’s rare photos

Pictures removed from public view as courts decide ownership
‘Fashion has to be fun. It’s a big business, not a cure for cancer’

‘Fashion has to be fun. It’s a big business, not a cure for cancer’

Donatella Versace at New York Fashion Week