Month: April 2018

Deciding whether a statement is true is a computational head-scratcher.

In the 1930s, Alan Turing showed there are basic tasks that are impossible to achieve by algorithmic means. In modern lingo, what he showed was that there can be no general computer program that answers yes or no to the question of whether another computer program will eventually stop when it is run.

The amazing unsolvability of this Halting Problem contains a further perplexing subtlety. While we have no way of finding in advance if a program will halt, there is an obvious way, in principle, to demonstrate that it halts if it is a halting program: run it, wait, and witness it halting!

In other words, Turing showed that, at the broadest level, deciding whether a statement is true is computationally harder than demonstrating that it’s true when it is.

A question of efficiency

Turing’s work was a pivotal moment in the history of computing. Some 80 years later, computing devices have pervaded almost every facet of society. Turing’s original “what is computable?” question has been mostly replaced by the more pertinent, “what is efficiently computable?”

But while Turing’s Halting Problem can be proved impossible in a few magical lines, the boundary between “efficient” and “inefficient” seems far more elusive. P versus NP is the most famous of a huge swathe of unresolved questions to have emerged from this modern take on Turing’s question.

So what is this NP thing?

Roughly speaking, P (standing for “polynomial time”), corresponds to the collection of computational problems that have an efficient solution. It’s only an abstract formulation of “efficient”, but it works fairly well in practice.

The class NP corresponds to the problems for which, when the answer is “yes”, there is an efficient demonstration that the answer is yes (the “N” stands for “nondeterministic”, but the description taken here is more intuitive). P versus NP simply asks if these two classes of computational problems are the same.

It’s just the “deciding versus demonstrating” issue in Turing’s original Halting Problem, but with the added condition of efficiency.

A puzzler

P certainly doesn’t look to be the same as NP. Puzzles are good examples of the general intuition here. Crossword puzzles are popular because it’s a challenge to find the solution, and humans like challenge. But no-one spends their lunchtime checking already completed crosswords: checking someone else’s solution offers nowhere near the same challenge.

Even clearer is Sudoku: again it is a genuine challenge to solve, but checking an existing solution for correctness is so routine it is devoid of entertainment value.

The P=NP possibility is like discovering that the “finding” part of these puzzles is only of the same difficulty to the “checking” part. That seems hard to believe, but the truth is we do not know for sure.

This same intuition pervades an enormous array of important computational tasks for which we don’t currently have efficient algorithms. One particularly tantalising feature is that, more often than not, these problems can be shown to be maximally hard among NP problems.

These so-called “NP-complete” problems are test cases for P versus NP: if any one of them has an efficient algorithmic solution then they all do (and efficient checking is no harder than efficient finding).

But if even just one single one can be shown to have no efficient solution, then P does not equal NP (and efficient finding really is, in general, harder than efficient checking).

Here are some classic examples of NP-complete problems.

• Partition (the dilemma of the alien pick-pockets). On an alien planet, two pick-pockets steal a wallet. To share the proceeds, they must evenly divide the money: can they do it? Standard Earth currencies evolved to have coin values designed to make this task easy, but in general this task is NP-complete. It’s in NP because, if there is an equal division of the coins, this can be easily demonstrated by simply showing the division. (Finding it is the hard part!)
• Timetabling. Finding if a clash-free timetable exists is NP-complete. The problem is in NP because we can efficiently check a correct, clash-free timetable to be clash-free.
• Travelling Salesman. A travelling salesman must visit each of some number of cities. To save costs, the salesman wants to find the shortest route that passes through all of the cities. For some given target distance “n”, is there a route of length at most “n”?
• Short proofs. Is there a short proof for your favourite mathematical statement (a Millennium Prize problem perhaps)? With a suitable formulation of “short”, this is NP-complete. It is in NP because checking formal proofs can be done efficiently: the hard part is finding them (at least, we think that’s the hard part!).

In every case, we know of no efficient exact algorithm, and the nonexistence of such an algorithm is equivalent to proving P not equal to NP.

So are we close to a solution? It seems the best we know is that we don’t know much! Arguably, the most substantial advances in the P versus NP saga are curiously negative: they mostly show we cannot possibly hope to resolve P as different to NP by familiar techniques.

We know Turing’s approach cannot work. In 2007, Alexander Razborov and Steven Rudich were awarded the Gödel Prize (often touted as the Nobel Prize of Computer Science) for their work showing that no “natural proof” can prove P unequal to NP.

Of course, we’ll keep looking!

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Marcel Jackson*

If one grossly divides mathematics into two parts they would be: tools for measuring and tools for recognition.

To use an analogy, tools for measuring are the technologies for collecting data about an object, the process of “taking a blurry photograph”. Tools for recognition deal with the following: if you are given a pile of data or a blurry photograph, how can the object that it came from be recognised from the data?

The Hodge Conjecture – a major unsolved problem in algebraic geometry – deals with recognition.

William Vallance Douglas Hodge was a professor at Cambridge who, in the 1940s, worked on developing a refined version of cohomology – tools for measuring flow and flux across boundaries of surfaces (for example, fluid flow across membranes).

The classical versions of cohomology are used for the understanding of the flow and dispersion of electricity and magnetism (for example, Maxwell’s equations, which describe how electric charges and currents act as origins for electric and magnetic fields). These were refined by Hodge in what is now called the “Hodge decomposition of cohomology”.

Hodge recognised that the actual measurements of flow across regions always contribute to a particular part of the Hodge decomposition, known as the (p,p) part. He conjectured that any time the data displays a contribution to the (p,p) part of the Hodge decomposition, the measurements could have come from a realistic scenario of a system of flux and change across a region.

Or, to put this as an analogy, one could say Hodge found a criterion to test for fraudulent data.

If Hodge’s test comes back positive, you can be sure the data is fraudulent. The question in the Hodge conjecture is whether there is any fraudulent data which Hodge’s test will not detect. So far, Hodge’s test seems to work.

But we haven’t understood well enough why it works, and so the possibility is open that there could be a way to circumvent Hodge’s security scheme.

Hodge made his conjecture in 1950, and many of the leaders in the development of geometry have worked on this basic recognition problem. The problem itself has stimulated many other refined techniques for measuring flow, flux and dispersion.

Tate’s 1963 conjecture is another similar recognition question coming out of another measurement technique, the l-adic cohomology developed by Alexander Grothendieck.

The strongest evidence in favour of the Hodge conjecture is a 1995 result of Cattani, Deligne & Kaplan which studies how the Hodge decomposition behaves as a region mutates.

Classical cohomology measurements are not affected by small mutations, but the Hodge decomposition does register mutations. The study of the Hodge decomposition across mutations provides great insight into the patterns in data that must occur in true measurements.

In the 1960s, Grothendieck initiated a powerful theory generalising the usual concept of “region” to include “virtual regions” (the theory of motives on which one could measure “virtual temperatures” and “virtual magnetic fields”.

In a vague sense, the theory of motives is trying to attack the problem by trying to think like a hacker. The “Standard Conjectures” of Grothendieck are far-reaching generalisations of the Hodge conjecture, which try to explain which virtual regions are indistinguishable from realistic scenarios.

The question in the Hodge conjecture has stimulated the development of revolutionary tools and techniques for measurement and analysis of data across regions. These tools have been, and continue to be, fundamental for modern development.

Imagine trying to building a mobile phone without an understanding of how to measure, analyse and control electricity and magnetism. Alternatively, imagine trying to sustain an environment without a way to measure, analyse and detect the spread of toxins across regions and in waterways.

Of course, the tantalising intrigue around recognition and detection problems makes them thrilling. Great minds are drawn in and produce great advances in an effort to understand what makes it all work.

One might, very reasonably, claim that the longer the Hodge conjecture remains an unsolved problem the more good it will do for humanity, driving more and more refined techniques for measurement and analysis and stimulating the development of better and better methods for recognition of objects from the data.

The Clay Mathematics Institute was wise in pinpointing the Hodge conjecture as a problem that has the capacity to stimulate extensive development of new methods and technologies and including it as one of the Millennium problems.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Arun Ram*

Among the seven problems in mathematics put forward by the Clay Mathematics Institute in 2000 is one that relates in a fundamental way to our understanding of the physical world we live in.

It’s the Navier-Stokes existence and uniqueness problem, based on equations written down in the 19th century.

The solution of this prize problem would have a profound impact on our understanding of the behaviour of fluids which, of course, are ubiquitous in nature. Air and water are the most recognisable fluids; how they move and behave has fascinated scientists and mathematicians since the birth of science.

But what are the so-called Navier-Stokes equations? What do they describe?

The equations

In order to understand the Navier-Stokes equations and their derivation we need considerable mathematical training and also a sound understanding of basic physics.

Without that, we must draw upon some very simple basics and talk in terms of broad generalities – but that should be sufficient to give the reader a sense of how we arrive at these fundamental equations, and the importance of the questions.

From this point, I’ll refer to the Navier-Stokes equations as “the equations”.

The equations governing the motion of a fluid are most simply described as a statement of Newton’s Second Law of Motion as it applies to the movement of a mass of fluid (whether that be air, water or a more exotic fluid). Newton’s second law states that:

Mass x Acceleration = Force acting on a body

For a fluid the “mass” is the mass of the fluid body; the “acceleration” is the acceleration of a particular fluid particle; the “forces acting on the body” are the total forces acting on our fluid.

Without going into full details, it’s possible to state here that Newton’s Second Law produces a system of differential equations relating rates of change of fluid velocity to the forces acting on the fluid. We require one other physical constraint to be applied on our fluid, which can be most simply stated as:

Mass is conserved! – i.e. fluid neither appears nor disappears from our system.

The solution

Having a sense of what the Navier-Stokes equations are allows us to discuss why the Millennium Prize solution is so important. The prize problem can be broken into two parts. The first focuses on the existence of solutions to the equations. The second focuses on whether these solutions are bounded (remain finite).

It’s not possible to give a precise mathematical description of these two components so I’ll try to place the two parts of the problem in a physical context.

1) For a mathematical model, however complicated, to represent the physical world we are trying to understand, the model must first have solutions.

At first glance, this seems a slightly strange statement – why study equations if we are not sure they have solutions? In practice we know many solutions that provide excellent agreement with many physically relevant and important fluid flows.

But these solutions are approximations to the solutions of the full Navier-Stokes equations (the approximation comes about because there is, usually, no simple mathematical formulae available – we must resort to solving the equations on a computer using numerical approximations).

Although we are very confident that our (approximate) solutions are correct, a formal mathematical proof of the existence of solutions is lacking. That provides the first part of the Millennium Prize challenge.

2) The second part asks whether the solutions of the Navier-Stokes equations can become singular (or grow without limit).

Again, a lot of mathematics is required to explain this. But we can examine why this is an important question.

There is an old saying that “nature abhors a vacuum”. This has a modern parallel in the assertion by physicist Stephen Hawking, while referring to black holes, that “nature abhors a naked singularity”. Singularity, in this case, refers to the point at which the gravitational forces – pulling objects towards a black hole – appear (according to our current theories) to become infinite.

In the context of the Navier-Stokes equations, and our belief that they describe the movement of fluids under a wide range of conditions, a singularity would indicate we might have missed some important, as yet unknown, physics. Why? Because mathematics doesn’t deal in infinites.

The history of fluid mechanics is peppered with solutions of simplified versions of the Navier-Stokes equations that yield singular solutions. In such cases, the singular solutions have often hinted at some new physics previously not considered in the simplified models.

Identifying this new physics has allowed researchers to further refine their mathematical models and so improve the agreement between model and reality.

If, as many believe, the Navier-Stokes equations do posses singular solutions then perhaps the next Millennium Prize will go to the person that discovers just what new physics is required to remove the singularity.

Then nature can, as all fluid mechanists already do, come to delight in the equations handed down to us by Claude-Louis Navier and George Gabriel Stokes.

For more such insights, log into our website https://international-maths-challenge.com

Credit of the article given to Jim Denier, University of Adelaide

How fluids move has fascinated researchers since the birth of science.

Among the seven problems in mathematics put forward by the Clay Mathematics Institute in 2000 is one that relates in a fundamental way to our understanding of the physical world we live in.

It’s the Navier-Stokes existence and uniqueness problem, based on equations written down in the 19th century.

The solution of this prize problem would have a profound impact on our understanding of the behaviour of fluids which, of course, are ubiquitous in nature. Air and water are the most recognisable fluids; how they move and behave has fascinated scientists and mathematicians since the birth of science.

But what are the so-called Navier-Stokes equations? What do they describe?

The equations

In order to understand the Navier-Stokes equations and their derivation we need considerable mathematical training and also a sound understanding of basic physics.

Without that, we must draw upon some very simple basics and talk in terms of broad generalities – but that should be sufficient to give the reader a sense of how we arrive at these fundamental equations, and the importance of the questions.

From this point, I’ll refer to the Navier-Stokes equations as “the equations”.

The equations governing the motion of a fluid are most simply described as a statement of Newton’s Second Law of Motion as it applies to the movement of a mass of fluid (whether that be air, water or a more exotic fluid). Newton’s second law states that:

Mass x Acceleration = Force acting on a body

For a fluid the “mass” is the mass of the fluid body; the “acceleration” is the acceleration of a particular fluid particle; the “forces acting on the body” are the total forces acting on our fluid.

Without going into full details, it’s possible to state here that Newton’s Second Law produces a system of differential equations relating rates of change of fluid velocity to the forces acting on the fluid. We require one other physical constraint to be applied on our fluid, which can be most simply stated as:

Mass is conserved! – i.e. fluid neither appears nor disappears from our system.

The solution

Having a sense of what the Navier-Stokes equations are allows us to discuss why the Millennium Prize solution is so important. The prize problem can be broken into two parts. The first focuses on the existence of solutions to the equations. The second focuses on whether these solutions are bounded (remain finite).

It’s not possible to give a precise mathematical description of these two components so I’ll try to place the two parts of the problem in a physical context.

1) For a mathematical model, however complicated, to represent the physical world we are trying to understand, the model must first have solutions.

At first glance, this seems a slightly strange statement – why study equations if we are not sure they have solutions? In practice we know many solutions that provide excellent agreement with many physically relevant and important fluid flows.

But these solutions are approximations to the solutions of the full Navier-Stokes equations (the approximation comes about because there is, usually, no simple mathematical formulae available – we must resort to solving the equations on a computer using numerical approximations).

Although we are very confident that our (approximate) solutions are correct, a formal mathematical proof of the existence of solutions is lacking. That provides the first part of the Millennium Prize challenge.

2) The second part asks whether the solutions of the Navier-Stokes equations can become singular (or grow without limit).

Again, a lot of mathematics is required to explain this. But we can examine why this is an important question.

There is an old saying that “nature abhors a vacuum”. This has a modern parallel in the assertion by physicist Stephen Hawking, while referring to black holes, that “nature abhors a naked singularity”. Singularity, in this case, refers to the point at which the gravitational forces – pulling objects towards a black hole – appear (according to our current theories) to become infinite.

In the context of the Navier-Stokes equations, and our belief that they describe the movement of fluids under a wide range of conditions, a singularity would indicate we might have missed some important, as yet unknown, physics. Why? Because mathematics doesn’t deal in infinites.

The history of fluid mechanics is peppered with solutions of simplified versions of the Navier-Stokes equations that yield singular solutions. In such cases, the singular solutions have often hinted at some new physics previously not considered in the simplified models.

Identifying this new physics has allowed researchers to further refine their mathematical models and so improve the agreement between model and reality.

If, as many believe, the Navier-Stokes equations do posses singular solutions then perhaps the next Millennium Prize will go to the person that discovers just what new physics is required to remove the singularity.

Then nature can, as all fluid mechanists already do, come to delight in the equations handed down to us by Claude-Louis Navier and George Gabriel Stokes.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Jim Denier*