Million Dollar Prize for solving what?

[emilynghiem]

P vs NP Millennium Prize Problems - Business Insider

OK so I find this article about solving a math problem that is supposed to
relate to computer-related problem-solving.

CMI is giving out million dollar prizes for 7 math problems and this is one of them.
P vs NP Problem Clay Mathematics Institute

But it looks like to me, the answer is already known. And people just don't have a formal proof.
So how is proving it formally going to solve anything?

Only if it is proven otherwise, that there CAN be a computer program to
generate solutions from a problem -- without going through "brute force/trial and error"
checking all the possibilities -- is that going to change anything.

It looks like it is already assumed that
"NP problems" where it is easy to CHECK if solutions work or not
do not guarantee or have a way to GENERATE solutions that work.

Am I reading this right?

What would be worth Millions if not Billions is if someone can write a computer/algorithm
for taking required conditions, and "generating" solutions from them without going through
the hard way, of generating all possible routes, and then checking to eliminate the contradictions,
which is the whole issue and point of addressing this in the first place.

But it looks like CMI wants to pay the prize money even if someone "formally proves"
this is impossible. Why? What difference does it make to "prove it formally" that it cannot be done?

Sorry if this goes under Education or somewhere else.
Since the original article was about the application to Finance and business security applications
I guessed to post it here. Is there a math and science section where this goes? Thanks!

 

[jwoodie]

Can you explain this question/problem? There are an infinite number of criteria that could be used to produce the requested list; however, there are only a limited number of combinations available (~N factorial). What is there to prove?

 

[emilynghiem]

Can you explain this question/problem? There are an infinite number of criteria that could be used to produce the requested list; however, there are only a limited number of combinations available (~N factorial). What is there to prove?

They want a "mathematical proof" that problems of the nature NP
are inconsistent problems of the nature P.

Everyone assumes this, but cannot prove it.

The opposite is easy, it can be proven that problems which DO have
algorithms for generating solutions also belong to the set of problems that can be checked
after possible solutions are offered. But not vice versa.

Frankly I don't see the benefit in proving it.
I only see the benefit in proving it is possible and fixable, and there is a method of generating solutions.

So that's what has me puzzled.
Why is this such a big deal to prove it is not possible to solve these types of problems easily?

Wouldn't the big deal be to prove that such problems can be solved,
and not hard to solve if everyone already assumes this to be true?

 

[emilynghiem]

One of the deepest questions in science is called P vs. NP, and answering the question would earn you a million-dollar prize. P vs. NP is one of the Clay Mathematics Institute Millennium Prize Problems, seven problems judged to be among the most important open questions in mathematics.

P vs. NP is about finding algorithms, or computer programs, to solve particular math problems, and whether or not "good" algorithms exist to solve these problems. Good algorithms allow a COMPUTER to come up with a solution to a problem relatively quickly, even if the size of the input to the problem is very large. Problems for which computer scientists have found good algorithms are said to be in the "complexity class" P.

However, there are a large number of problems for which the best-known algorithms are not efficient, and can take an extremely long time to run on even the fastest computers. Some of these problems have very important applications to computer and industrial design, internet security, and resource allocation. Problems that have a good algorithm for checking a given possible solution but that don't necessarily have a good algorithm for finding solutions are in the complexity class NP.

The million-dollar question is whether the two complexity classes P and NP equal each other. P is contained in NP: Any problem that can be solved quickly by a COMPUTER can also have a particular possible answer quickly checked by a computer. The reverse — whether NP is contained in P — is unknown: We don't know whether problems that have a good algorithm for checking answers also have good algorithms for finding answers.

Most computer scientists and mathematicians think that the two classes are not equal: that there are some problems in NP that are not in P. Yet this has never been mathematically proven. Finding efficient algorithms for the hard problems in NP, and showing that P = NP, would dramatically change the world. On the other hand, finding a proof that no such algorithms exist, and that P ≠ NP, would likely involve a huge leap in our understanding of the nature and limitations of computers.

 

[oldfart]

This is an outgrowth of linear programming theory from the early 40's. The fundamental form of the linear programming problem was demonstrated to have four possible and mutually exclusive solutions:
1. The solution set was a null set.
2. The solution set was unbounded.
3. There was a unique solution.
4. There were multiple solutions.

The computations required for certain problems exceeded the computational power all of the world's computers combined working non-stop for several centuries. The original SIMPLEX algorithm was proven to always move toward the solution, but it was not very efficient. This gave rise to two related questions:

1. Is it possible to quickly determine which of the four possible solutions applies before wasting a lot of effort on what may be a fruitless search?

2. What is the most efficient algorithm path to a solution?

Answering these questions requires a mathematical proof of the problems stated in the prize. The problem cannot be resolved by simply building computers with more computing power, as the range of problems requiring solutions unattainable by technology at any point in time seems to grow faster than technological change. If we want to use optimization models to analyze DNA and evolutionary genetics, solve questions in basic particle physics and cosmology, or even predict weather and climate change better or coordinate a trillion node transportation network, this basic problem has to be solved. It is one of the fundamental mathematical problems whose solution is required to move computation to a level that can deal with these issues.

 

[emilynghiem]

Thanks, oldfart!
What I am asking now is
A. If it is pretty much assumed there is no way to set up such algorithms,
what good does it do to prove "formally" if we already know the answer is going to be NOT POSSIBLE.
B. If the point IS to prove a way to set up such an algorithm, or an algorithm for finding an algorithm,
or an algorithm for finding an algorithm for various algorithm, etc.
then WHY NOT state it that way? That the only valuable answer worth the prize money
IS to prove such a pattern EXISTS by FINDING and proving it works?
Why not just state that as the only answer worth anything, instead of
also offering if it is proven such an algorithm cannot be found, which is already assumed.

C. Are you saying that the question is really
1. in WHICH cases can an algorithm be found
2. in WHICH cases is there no such algorithm
And the POINT of the proof is to set up a pattern for
DISTINGUISHING NP from P problems?

And that is why it is stated as proving "either one"?

I think I am getting what you are saying if this is closer.
So thanks in advance! At least that much is clarified. Whew!

This is an outgrowth of linear programming theory from the early 40's. The fundamental form of the linear programming problem was demonstrated to have four possible and mutually exclusive solutions:
1. The solution set was a null set.
2. The solution set was unbounded.
3. There was a unique solution.
4. There were multiple solutions.

The computations required for certain problems exceeded the computational power all of the world's computers combined working non-stop for several centuries. The original SIMPLEX algorithm was proven to always move toward the solution, but it was not very efficient. This gave rise to two related questions:

1. Is it possible to quickly determine which of the four possible solutions applies before wasting a lot of effort on what may be a fruitless search?

2. What is the most efficient algorithm path to a solution?

Answering these questions requires a mathematical proof of the problems stated in the prize. The problem cannot be resolved by simply building computers with more computing power, as the range of problems requiring solutions unattainable by technology at any point in time seems to grow faster than technological change. If we want to use optimization models to analyze DNA and evolutionary genetics, solve questions in basic particle physics and cosmology, or even predict weather and climate change better or coordinate a trillion node transportation network, this basic problem has to be solved. It is one of the fundamental mathematical problems whose solution is required to move computation to a level that can deal with these issues.

 

[oldfart]

Thanks, oldfart!
What I am asking now is
A. If it is pretty much assumed there is no way to set up such algorithms, what good does it do to prove "formally" if we already know the answer is going to be NOT POSSIBLE.

The real question is not "Is a solution possible?", but "Under what conditions is a solution possible?" In the linear programming context where the question began, the basic form contains a constraint with a matrix A with dimensions m and n. The solution requires inverting that matrix; a formidable task as m and n get large (Leontifeff's model of the US economy got to about a 20,000 by 60,000 matrix by the 1960's which would have taken the fastest computer decades to solve at the time). But determining if the solution set was unbounded or a null set could be found by computing the determinant of the matrix, a task that would take a few days back then. So a mathematical proof that the simple test could determine if the problem was soluble or not had a lot of value.

B. If the point IS to prove a way to set up such an algorithm, or an algorithm for finding an algorithm, or an algorithm for finding an algorithm for various algorithm, etc. then WHY NOT state it that way?

We had an algorithm (the SIMPLEX algorithm) which was clunky, but worked. There is an ongoing endeavor to find more efficient "search paths" to shorten the number of computations needed to arrive at an optimal solution. The mathematical problem was to define "efficient search paths" and find a way to know for any class of problems if we had the most efficient search path to the optimal solution other than by simple trial and error.

C. Are you saying that the question is really
1. in WHICH cases can an algorithm be found
2. in WHICH cases is there no such algorithm
And the POINT of the proof is to set up a pattern for
DISTINGUISHING NP from P problems?

And that is why it is stated as proving "either one"?

I think I am getting what you are saying if this is closer.
So thanks in advance! At least that much is clarified. Whew!

You pretty much have it. There is a subset of linear programming problems where the answer (solution) had to be an integer. I worked on this a while in graduate school. The field began when the Navy tried to use linear programming to determine the composition of task forces for given missions. The first pass neglected to specify the answers had to be integers, and their first run suggest a task force that included 2.2 battleships and 4.5 aircraft carriers. It was suggested that the 0.5 carrier might not float.

In the 60's Lipsey and Lancaster published a famous paper on the "The Theory of the Second Best" in which they provided a proof that when an additional constraint (such as requiring integer solutions) is added, the ultimate optimal solution may be quite far from the preliminary optimal solution arrived at before adding the new constraint. This has obvious impact on economic theory, especially when considering supply jolts such as resource shortages as in the 1973 oil embargo.

It also turns out that a special application of integer programming is the basis for transportation network theory (think scheduling traffic on telecommunications trunk lines, electric power distribution grids, railroad and truck distribution routes, etc.). So L & L's work is part of the basis of how a technological society works, as well as the basis for much of modern management decision theory.

 

[emilynghiem]

Thanks so much!
Anyone who can explain something this user-unfriendly to make simple sense to me
is super special!

I wonder if the math genius who tutored me through school
is working on something like this. I should contact him and see what he is doing.

I can actually follow your explanation, so I can't be completely math-illiterate!

Thanks, oldfart!
What I am asking now is
A. If it is pretty much assumed there is no way to set up such algorithms, what good does it do to prove "formally" if we already know the answer is going to be NOT POSSIBLE.

The real question is not "Is a solution possible?", but "Under what conditions is a solution possible?" In the linear programming context where the question began, the basic form contains a constraint with a matrix A with dimensions m and n. The solution requires inverting that matrix; a formidable task as m and n get large (Leontifeff's model of the US economy got to about a 20,000 by 60,000 matrix by the 1960's which would have taken the fastest computer decades to solve at the time). But determining if the solution set was unbounded or a null set could be found by computing the determinant of the matrix, a task that would take a few days back then. So a mathematical proof that the simple test could determine if the problem was soluble or not had a lot of value.

B. If the point IS to prove a way to set up such an algorithm, or an algorithm for finding an algorithm, or an algorithm for finding an algorithm for various algorithm, etc. then WHY NOT state it that way?

We had an algorithm (the SIMPLEX algorithm) which was clunky, but worked. There is an ongoing endeavor to find more efficient "search paths" to shorten the number of computations needed to arrive at an optimal solution. The mathematical problem was to define "efficient search paths" and find a way to know for any class of problems if we had the most efficient search path to the optimal solution other than by simple trial and error.

C. Are you saying that the question is really
1. in WHICH cases can an algorithm be found
2. in WHICH cases is there no such algorithm
And the POINT of the proof is to set up a pattern for
DISTINGUISHING NP from P problems?

And that is why it is stated as proving "either one"?

I think I am getting what you are saying if this is closer.
So thanks in advance! At least that much is clarified. Whew!

You pretty much have it. There is a subset of linear programming problems where the answer (solution) had to be an integer. I worked on this a while in graduate school. The field began when the Navy tried to use linear programming to determine the composition of task forces for given missions. The first pass neglected to specify the answers had to be integers, and their first run suggest a task force that included 2.2 battleships and 4.5 aircraft carriers. It was suggested that the 0.5 carrier might not float.

In the 60's Lipsey and Lancaster published a famous paper on the "The Theory of the Second Best" in which they provided a proof that when an additional constraint (such as requiring integer solutions) is added, the ultimate optimal solution may be quite far from the preliminary optimal solution arrived at before adding the new constraint. This has obvious impact on economic theory, especially when considering supply jolts such as resource shortages as in the 1973 oil embargo.

It also turns out that a special application of integer programming is the basis for transportation network theory (think scheduling traffic on telecommunications trunk lines, electric power distribution grids, railroad and truck distribution routes, etc.). So L & L's work is part of the basis of how a technological society works, as well as the basis for much of modern management decision theory.