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
Life and Style
fashionHealth concerns and 'pornified' perceptions have made women more conscious at the beach
Arts and Entertainment
tv
Sport
Ojo Onaolapo celebrates winning the bronze medal
commonwealth games
Arts and Entertainment
Rock band Led Zeppelin in the early 1970s
musicLed Zeppelin to release alternative Stairway To Heaven after 43 years
Arts and Entertainment
High-flyer: Chris Pratt in 'Guardians of the Galaxy'
filmHe was homeless in Hawaii when he got his big break. Now the comic actor Chris Pratt is Hollywood's new favourite action star
Sport
Van Gaal said that his challenge in taking over Bobby Robson's Barcelona team in 1993 has been easier than the task of resurrecting the current United side
footballA colourful discussion on tactics, the merits of the English footballer and rebuilding Manchester United
Life and Style
Sainsbury's could roll the lorries out across its whole fleet if they are successful
tech
News
ebookA unique anthology of reporting and analysis of a crucial period of history
Travel
The shipping news: a typical Snoozebox construction
travelSpending the night in a shipping container doesn't sound appealing, but mobile crash pads are popping up at the summer's biggest events
Arts and Entertainment
'Old Fashioned' will be a different kind of love story to '50 Shades'
film
Arts and Entertainment
Tracey Emin's 'My Bed' is returning to the Tate more than 15 years after it first caused shockwaves at the gallery
artTracey Emin's bed returns to the Tate after record sale
Arts and Entertainment
Smart mover: Peter Bazalgette
filmHow live cinema screenings can boost arts audiences
Environment
Neil Young performing at Hyde Park, London, earlier this month
environment
Independent
Travel Shop
the manor
Up to 70% off luxury travel
on city breaks Find out more
santorini
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
and  

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

iJobs Job Widget
iJobs General

Project Coordinator

Competitive: The Green Recruitment Company: The Organisation: The Green Recrui...

Project Manager (HR)- Bristol - Upto £400 p/day

£350 - £400 per annum + competitive: Orgtel: Project Manager (specializing in ...

Embedded Linux Engineer

£40000 - £50000 per annum + competitive: Progressive Recruitment: Embedded Sof...

Senior Hardware Design Engineer - Broadcast

£50000 - £65000 per annum + Benefits: Progressive Recruitment: Working for a m...

Day In a Page

Save the tiger: The animals bred for bones on China’s tiger farms

The animals bred for bones on China’s tiger farms

The big cats kept in captivity to perform for paying audiences and then, when dead, their bodies used to fortify wine
A former custard factory, a Midlands bog and a Leeds cemetery all included in top 50 hidden spots in the UK

A former custard factory, a Midlands bog and a Leeds cemetery

Introducing the top 50 hidden spots in Britain
Ebola epidemic: Plagued by fear

Ebola epidemic: Plagued by fear

How a disease that has claimed fewer than 2,000 victims in its history has earned a place in the darkest corner of the public's imagination
Chris Pratt: From 'Parks and Recreation' to 'Guardians of the Galaxy'

From 'Parks and Recreation' to 'Guardians of the Galaxy'

He was homeless in Hawaii when he got his big break. Now the comic actor Chris Pratt is Hollywood's new favourite action star
How live cinema screenings can boost arts audiences

How live cinema screenings can boost arts audiences

Broadcasting plays and exhibitions to cinemas is a sure-fire box office smash
Shipping container hotels: Pop-up hotels filling a niche

Pop-up hotels filling a niche

Spending the night in a shipping container doesn't sound appealing, but these mobile crash pads are popping up at the summer's biggest events
Native American headdresses are not fashion accessories

Feather dust-up

A Canadian festival has banned Native American headwear. Haven't we been here before?
Boris Johnson's war on diesel

Boris Johnson's war on diesel

11m cars here run on diesel. It's seen as a greener alternative to unleaded petrol. So why is London's mayor on a crusade against the black pump?
5 best waterproof cameras

Splash and flash: 5 best waterproof cameras

Don't let water stop you taking snaps with one of these machines that will take you from the sand to meters deep
Louis van Gaal interview: Manchester United manager discusses tactics and rebuilding after the David Moyes era

Louis van Gaal interview

Manchester United manager discusses tactics and rebuilding after the David Moyes era
Will Gore: The goodwill shown by fans towards Alastair Cook will evaporate rapidly if India win the series

Will Gore: Outside Edge

The goodwill shown by fans towards Alastair Cook will evaporate rapidly if India win the series
The children were playing in the street with toy guns. The air strikes were tragically real

The air strikes were tragically real

The children were playing in the street with toy guns
Boozy, ignorant, intolerant, but very polite – The British, as others see us

Britain as others see us

Boozy, ignorant, intolerant, but very polite
How did our legends really begin?

How did our legends really begin?

Applying the theory of evolution to the world's many mythologies
Watch out: Lambrusco is back on the menu

Lambrusco is back on the menu

Naff Seventies corner-shop staple is this year's Aperol Spritz