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.

Voices
Hunted: A stag lies dead on Jura, where David Cameron holidays and has himself stalked deer
voicesThe Scotland I know is becoming a playground for the rich
News
Russell Brand has written a book of political analysis called Revolution
peopleFilm star says he is 'not interested in making money anymore'
Arts and Entertainment
Benedict Cumberbatch has refused to deny his involvement in the upcoming new Star Wars film
filmBenedict Cumberbatch reignites those Star Wars rumours
News
newsMcKamey Manor says 'there is no escape until the tour is completed'
PROMOTED VIDEO
Arts and Entertainment
Jessica Chastain during an interview in Los Angeles.
filmsOscar hopeful Jessica Chastain reveals the secret to her breakthrough success
News
people

Britain First criticised for using actress's memory to draw attention to their 'hate-filled home page'

News
news
Life and Style
Meow! ... Again, Kim Kardashian goes for a sexy Halloween costume, wrapping her body with a latex catsuit and high heeled knee boots
fashionFrom Heidi Klum to Kim Kardashian
News
news

Emergency call 'started off dumb, but got pretty serious'

Arts and Entertainment
On The Apprentice, “serious” left the room many moons ago and yet still we watch
tv

Greatest mystery about the hit BBC1 show is how it continues to be made at all, writes Grace Dent

News
ebooksAn unforgettable anthology of contemporary reportage
News
i100
Arts and Entertainment
JK Rowling is releasing a new Harry Potter story about Dolores Umbridge
booksChristmas comes early for wizard fans
Arts and Entertainment
filmsOculus Rift offers breathtakingly realistic simulation of zero gravity
Sport
footballAccording to revelations from Sergio Aguero's new biography
Life and Style
tech

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

Business Analyst - Surrey - Permanent - Up to £50k DOE

£40000 - £50000 Per Annum Excellent benefits: Clearwater People Solutions Ltd:...

***ASP.NET Developer - Cheshire - £35k - Permanent***

£30000 - £35000 Per Annum Excellent benefits: Clearwater People Solutions Ltd:...

***Solutions Architect*** - Brighton - £40k - Permanent

£35000 - £40000 Per Annum Excellent benefits: Clearwater People Solutions Ltd:...

Senior Research Fellow in Gender, Food and Resilient Communities

£47,334 - £59,058 per annum: Coventry University: The Centre for Agroecology, ...

Day In a Page

Wilko Johnson, now the bad news: musician splits with manager after police investigate assault claims

Wilko Johnson, now the bad news

Former Dr Feelgood splits with manager after police investigate assault claims
Mark Udall: The Democrat Senator with a fight on his hands ahead of the US midterm elections

Mark Udall: The Democrat Senator with a fight on his hands

The Senator for Colorado is for gay rights, for abortion rights – and in the Republicans’ sights as they threaten to take control of the Senate next month
New discoveries show more contact between far-flung prehistoric humans than had been thought

New discoveries show more contact between far-flung prehistoric humans than had been thought

Evidence found of contact between Easter Islanders and South America
Cerys Matthews reveals how her uncle taped 150 interviews for a biography of Dylan Thomas

Cerys Matthews on Dylan Thomas

The singer reveals how her uncle taped 150 interviews for a biography of the famous Welsh poet
DIY is not fun and we've finally realised this as a nation

Homebase closures: 'DIY is not fun'

Homebase has announced the closure of one in four of its stores. Nick Harding, who never did know his awl from his elbow, is glad to see the back of DIY
The Battle of the Five Armies: Air New Zealand releases new Hobbit-inspired in-flight video

Air New Zealand's wizard in-flight video

The airline has released a new Hobbit-inspired clip dubbed "The most epic safety video ever made"
Pumpkin spice is the flavour of the month - but can you stomach the sweetness?

Pumpkin spice is the flavour of the month

The combination of cinnamon, clove, nutmeg (and no actual pumpkin), now flavours everything from lattes to cream cheese in the US
11 best sonic skincare brushes

11 best sonic skincare brushes

Forget the flannel - take skincare to the next level by using your favourite cleanser with a sonic facial brush
Paul Scholes column: I'm not worried about Manchester United's defence - Chelsea test can be the making of Phil Jones and Marcos Rojo

Paul Scholes column

I'm not worried about Manchester United's defence - Chelsea test can be the making of Jones and Rojo
Frank Warren: Boxing has its problems but in all my time I've never seen a crooked fight

Frank Warren: Boxing has its problems but in all my time I've never seen a crooked fight

While other sports are stalked by corruption, we are an easy target for the critics
Jamie Roberts exclusive interview: 'I'm a man of my word – I'll stay in Paris'

Jamie Roberts: 'I'm a man of my word – I'll stay in Paris'

Wales centre says he’s not coming home but is looking to establish himself at Racing Métro
How could three tourists have been battered within an inch of their lives by a burglar in a plush London hotel?

A crime that reveals London's dark heart

How could three tourists have been battered within an inch of their lives by a burglar in a plush London hotel?
Meet 'Porridge' and 'Vampire': Chinese state TV is offering advice for citizens picking a Western moniker

Lost in translation: Western monikers

Chinese state TV is offering advice for citizens picking a Western moniker. Simon Usborne, who met a 'Porridge' and a 'Vampire' while in China, can see the problem
Handy hacks that make life easier: New book reveals how to rid your inbox of spam, protect your passwords and amplify your iPhone

Handy hacks that make life easier

New book reveals how to rid your email inbox of spam, protect your passwords and amplify your iPhone with a loo-roll
KidZania lets children try their hands at being a firefighter, doctor or factory worker for the day

KidZania: It's a small world

The new 'educational entertainment experience' in London's Shepherd's Bush will allow children to try out the jobs that are usually undertaken by adults, including firefighter, doctor or factory worker