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.

Start your day with The Independent, sign up for daily news emails
News
newsAnother week, another dress controversy on the internet
Life and Style
Scientist have developed a test which predicts whether you'll live for another ten years
health
Life and Style
Marie had fake ID, in the name of Johanna Koch, after she evaded capture by the Nazis in wartime Berlin
historyOne woman's secret life as a Jew in wartime Berlin
News
news... and what your reaction to the creatures above says about you
ebooks
ebooksA special investigation by Andy McSmith
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

Recruitment Genius: Telesales & Customer Service Executive - Call Centre Jobs

£7 - £9 per hour: Recruitment Genius: Are you outgoing? Do you want to work in...

Ashdown Group: Finance Manager - Covent Garden, central London - £45k - £55k

£45000 - £55000 per annum + 30 days holiday: Ashdown Group: Finance Manager - ...

Ashdown Group: Systems Administrator - Lancashire - £30,000

£28000 - £30000 per annum: Ashdown Group: 3rd Line Support Engineer / Network ...

Recruitment Genius: Graduate Web Developer

£26000 - £33000 per annum: Recruitment Genius: A Web Developer is required to ...

Day In a Page

Syrian conflict is the world's first 'climate change war', say scientists, but it won't be the last one

Climate change key in Syrian conflict

And it will trigger more war in future
How I outwitted the Gestapo

How I outwitted the Gestapo

My life as a Jew in wartime Berlin
The nation's favourite animal revealed

The nation's favourite animal revealed

Women like cuddly creatures whilst men like creepy-crawlies
Is this the way to get young people to vote?

Getting young people to vote

From #VOTESELFISH to Bite the Ballot
Poldark star Heida Reed: 'I don't think a single bodice gets ripped'

Poldark star Heida Reed

'I don't think a single bodice gets ripped'
The difference between America and Israel? There isn’t one

The difference between America and Israel? There isn’t one

Netanyahu knows he can get away with anything in America, says Robert Fisk
Families clubbing together to build their own affordable accommodation

Do It Yourself approach to securing a new house

Community land trusts marking a new trend for taking the initiative away from developers
Head of WWF UK: We didn’t send Cameron to the Arctic to see green ideas freeze

David Nussbaum: We didn’t send Cameron to the Arctic to see green ideas freeze

The head of WWF UK remains sanguine despite the Government’s failure to live up to its pledges on the environment
Author Kazuo Ishiguro on being inspired by shoot-outs and samurai

Author Kazuo Ishiguro on being inspired by shoot-outs and samurai

Set in a mythologised 5th-century Britain, ‘The Buried Giant’ is a strange beast
With money, corruption and drugs, this monk fears Buddhism in Thailand is a ‘poisoned fruit’

Money, corruption and drugs

The monk who fears Buddhism in Thailand is a ‘poisoned fruit’
America's first slavery museum established at Django Unchained plantation - 150 years after slavery outlawed

150 years after it was outlawed...

... America's first slavery museum is established in Louisiana
Kelly Clarkson: How I snubbed Simon Cowell and become a Grammy-winning superstar

Kelly Clarkson: How I snubbed Simon Cowell and become a Grammy-winning superstar

The first 'American Idol' winner on how she manages to remain her own woman – Jane Austen fascination and all
Tony Oursler on exploring our uneasy relationship with technology with his new show

You won't believe your eyes

Tony Oursler's new show explores our uneasy relationship with technology. He's one of a growing number of artists with that preoccupation
Ian Herbert: Peter Moores must go. He should never have been brought back to fail again

Moores must go. He should never have been brought back to fail again

The England coach leaves players to find solutions - which makes you wonder where he adds value, says Ian Herbert
War with Isis: Fears that the looming battle for Mosul will unleash 'a million refugees'

The battle for Mosul will unleash 'a million refugees'

Aid agencies prepare for vast exodus following planned Iraqi offensive against the Isis-held city, reports Patrick Cockburn