My Math Forum > Math My "P=NP" Explanation

 Math General Math Forum - For general math related discussion and news

 View Poll Results: Am I wrong or Simply Correct? Simply Correct 2 66.67% Wrong 1 33.33% Voters: 3. You may not vote on this poll

January 9th, 2017, 10:59 AM   #11
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 1,791
Thanks: 576

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
 Originally Posted by TwoCoins Question: "If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? this is the essence of the P vs NP question.
I think you're a little confused as to the difference between P and NP problems. P and NP are defined according to whether some sort of algorithm is directly computable by a turing machine (deterministic) or whether the algorithm requires some sort of trial and error guesswork (non-deterministic). The easy/hard nature of those is about best-case complexity. Not all P problems are 'easy' and not all NP problems are 'hard' although P problems tend to be 'easier' for sure.

Quote:
 Typical of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit, how can one do this without visiting a city twice? if you give me a solution, I can easily check that it is correct. But I cannot so easily find a solution." I am mainly going off the main question here " If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem?" My Answer: Yes: P=NP If you can check that a solution is correct easily then you "know" the solution therefore the problem is also easy to solve. It's asking if 1=1.
No, they are very distinct beasts. For example, asking someone to answer the question "How long is Crewe Alexandra's football field?" is very different to asking "Is Crewe Alexandra's football field 1m long?". The second question is easy to answer because even with no prior knowledge of football fields, you can arrive at the football field, walk 1m with your measuring device, and then find that the football field is much larger by taking a few more steps. The first one is harder because it actually requires going to a football field and measuring it properly and walking the whole length of the field.

Let's consider some algorithms. You could basically follow these steps to measure the length of the field:

1. Walk forward 1m.
2. Check: are you at the end of the field?
3. If so, print result. If not, go to 1.

This algorithm has polynomial complexity, but we have no idea how many steps we are going to take until we actually measure the length. Now, let's say, for the sake of argument, that all football fields were made according to a formula:

$\displaystyle f(N) = 100 + 0.0001N$

where N is the capacity of the stadium and f(N) is the length of the football field. We know that Crewe Alexandra has a capacity of 6000. What is the result? The algorithm is as follows:

1. Multiply 0.0001 by N
2. Add 100 to the result
3. print result

No matter what stadium you have, this algorithm is always going to give a result that is directly computable; no checks needed. Therefore, the algorithm is a P algorithm. It is always evaluable in 3 steps, making it "easy". Even though the value is constant, we consider this polynomial space, so we just say that the algorithm is evaluable in polynomial time.

Quote:
 Solving the problem would make it correct/solved. If you can easily check the problem is correct then you have solved the problem.
It is trivially true to say that if you know the answer, a check will pass, but what if you don't know the solution? What if the check you were asked to perform was crazy, like "Is Crewe Alexandra's football pitch 100000 m long?" You will have to walk the whole football field just to find out and then you've already solved the problem the hard way!

Basically, evaluating a result directly and checking whether some existing result is correct are different things and should be treated differently.

In complexity terms, your Hamiltonian path finding is an NP-hard problem, where the number of guesses that is typically needed to obtain a correct result sky-rockets with the number of entities in your problem.

Quote:
 Solving a problem using some sort of NP No: P does not = NP The only way this is possible is if you do not know there is a problem and P=0 If you cannot easily check that the problem is correct then you have yet to find the problem/solve it therefore you cannot begin to easily correct the problem or solve it.
Some people think that P is a subset of NP. That is, all P problems can be calculated using NP algorithms (Note it should be $\displaystyle P \subseteq NP$). The existence of numerical methods seems to suggest that, but there is just no formal proof of it (yet?).

January 9th, 2017, 12:07 PM   #12
Newbie

Joined: Jan 2017
From: United States

Posts: 9
Thanks: 0

Quote:
 Originally Posted by Benit13 I think you're a little confused as to the difference between P and NP problems. P and NP are defined according to whether some sort of algorithm is directly computable by a turing machine (deterministic) or whether the algorithm requires some sort of trial and error guesswork (non-deterministic). The easy/hard nature of those is about best-case complexity. Not all P problems are 'easy' and not all NP problems are 'hard' although P problems tend to be 'easier' for sure. No, they are very distinct beasts. For example, asking someone to answer the question "How long is Crewe Alexandra's football field?" is very different to asking "Is Crewe Alexandra's football field 1m long?". The second question is easy to answer because even with no prior knowledge of football fields, you can arrive at the football field, walk 1m with your measuring device, and then find that the football field is much larger by taking a few more steps. The first one is harder because it actually requires going to a football field and measuring it properly and walking the whole length of the field. Let's consider some algorithms. You could basically follow these steps to measure the length of the field: 1. Walk forward 1m. 2. Check: are you at the end of the field? 3. If so, print result. If not, go to 1. This algorithm has polynomial complexity, but we have no idea how many steps we are going to take until we actually measure the length. Now, let's say, for the sake of argument, that all football fields were made according to a formula: $\displaystyle f(N) = 100 + 0.0001N$ where N is the capacity of the stadium and f(N) is the length of the football field. We know that Crewe Alexandra has a capacity of 6000. What is the result? The algorithm is as follows: 1. Multiply 0.0001 by N 2. Add 100 to the result 3. print result No matter what stadium you have, this algorithm is always going to give a result that is directly computable; no checks needed. Therefore, the algorithm is a P algorithm. It is always evaluable in 3 steps, making it "easy". Even though the value is constant, we consider this polynomial space, so we just say that the algorithm is evaluable in polynomial time. It is trivially true to say that if you know the answer, a check will pass, but what if you don't know the solution? What if the check you were asked to perform was crazy, like "Is Crewe Alexandra's football pitch 100000 m long?" You will have to walk the whole football field just to find out and then you've already solved the problem the hard way! Basically, evaluating a result directly and checking whether some existing result is correct are different things and should be treated differently. In complexity terms, your Hamiltonian path finding is an NP-hard problem, where the number of guesses that is typically needed to obtain a correct result sky-rockets with the number of entities in your problem. Some people think that P is a subset of NP. That is, all P problems can be calculated using NP algorithms (Note it should be $\displaystyle P \subseteq NP$). The existence of numerical methods seems to suggest that, but there is just no formal proof of it (yet?).

"This algorithm has polynomial complexity, but we have no idea how many steps we are going to take until we actually measure the length."

This is the essence of life. We "think" we know until we "actually" get there and THEN we find the "correct" truth and correlation. From your own problem experiences to the world's problem experiences together as a whole. We are essentially evolving together yet separately by solving more problems because well more people, more problems, more experiences.. etc. This is the ONLY circumstance in which P will = NP. Math, History, Science, and even languages work this way. It's pretty much the essence of how we "learn". Think of "knowing" as like a ladder to climb. If you are missing steps to your ladder it will be much harder to climb. If you blindly mistake that you already know something you will also miss a step completely blind. Always stay humble and be aware so you can climb at a much steadier pace. P doesnt = NP if you give up.

January 11th, 2017, 02:55 AM   #13
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 1,791
Thanks: 576

Math Focus: Physics, mathematical modelling, numerical and computational solutions
I'm really sorry, but I just can't resist... I haven't had my coffee yet and this post was just too funny.

Quote:
 Originally Posted by TwoCoins "This algorithm has polynomial complexity, but we have no idea how many steps we are going to take until we actually measure the length." This is the essence of life.
Lovely.

Quote:
 We "think" we know until we "actually" get there and THEN we find the "correct" truth and correlation.
Well... sometimes we have a good idea how long something is going to take because of convergence diagnostics or statistical analysis... in fact, one could argue that the whole point of studying complexity classes is to be able to compare computer algorithms that solve the same problem and allow us to pick the the fastest one as possible.

Quote:
 From your own problem experiences to the world's problem experiences together as a whole.
I wonder what the complexity class is for first world problems!

Quote:
 We are essentially evolving together yet separately by solving more problems because well more people, more problems, more experiences.. etc.
By the way... evolution by natural/man-made selection is not a random problem, but a very complex one, so the algorithms that approximate it are NP problems. I have a colleague who is an expert in those because he writes optimization algorithms using them

Quote:
 This is the ONLY circumstance in which P will = NP.
Eh?

Quote:
 Math, History, Science, and even languages work this way.
They change over time, sure, but that has nothing to do with complexity classes. I don't think algorithms exist that track the 'progress' of maths, history and science, although scientists occasionally perform statistical diagnostics on journal paper submissions to try and learn about scientific progress (although most take those studies well cooked with a fair dose of salt and pepper).

Quote:
 It's pretty much the essence of how we "learn".
Naaaah... this is how learning more or less happens...

1. Pick a thing that looks cool (that you don't know already)
3. Try doing it
4. Can you do it yet? If not, try going back to 2 or 3
5. If so, go back to 1

Actually... that's an NP problem

Quote:
 Think of "knowing" as like a ladder to climb. If you are missing steps to your ladder it will be much harder to climb.
I'm happy that your study of complexity classes has allowed you to understand learning, but maybe you should look at pedagogy rather than complexity classes to derive wisdom about learning.

Quote:
 If you blindly mistake that you already know something you will also miss a step completely blind. Always stay humble and be aware so you can climb at a much steadier pace. P doesnt = NP if you give up.
Well, I'm not working on complexity classes, so I don't care whether $\displaystyle P \subseteq NP$ or not, but I'm sure there'll be some guys working on the problem that will feel revitalized by your pep talk.

Last edited by Benit13; January 11th, 2017 at 02:56 AM. Reason: added a winky face at the bottom ;)

January 11th, 2017, 08:35 AM   #14
Newbie

Joined: Jan 2017
From: United States

Posts: 9
Thanks: 0

Quote:
 Originally Posted by Benit13 I'm really sorry, but I just can't resist... I haven't had my coffee yet and this post was just too funny. Lovely. Well... sometimes we have a good idea how long something is going to take because of convergence diagnostics or statistical analysis... in fact, one could argue that the whole point of studying complexity classes is to be able to compare computer algorithms that solve the same problem and allow us to pick the the fastest one as possible. I wonder what the complexity class is for first world problems! By the way... evolution by natural/man-made selection is not a random problem, but a very complex one, so the algorithms that approximate it are NP problems. I have a colleague who is an expert in those because he writes optimization algorithms using them Eh? They change over time, sure, but that has nothing to do with complexity classes. I don't think algorithms exist that track the 'progress' of maths, history and science, although scientists occasionally perform statistical diagnostics on journal paper submissions to try and learn about scientific progress (although most take those studies well cooked with a fair dose of salt and pepper). Naaaah... this is how learning more or less happens... 1. Pick a thing that looks cool (that you don't know already) 2. Read something about it or listen to someone talking about it 3. Try doing it 4. Can you do it yet? If not, try going back to 2 or 3 5. If so, go back to 1 Actually... that's an NP problem I'm happy that your study of complexity classes has allowed you to understand learning, but maybe you should look at pedagogy rather than complexity classes to derive wisdom about learning. Well, I'm not working on complexity classes, so I don't care whether $\displaystyle P \subseteq NP$ or not, but I'm sure there'll be some guys working on the problem that will feel revitalized by your pep talk.

You aren't understanding a word I say. I find this normal among the people stuck in the numbers. You are off in this algorithm world where everything is "suppose" to be exact. When things are only "exact" when correct. You are thinking in terms way too complicated. You pick apart my post like I was making different conjectures when actually the whole thing was one point. This may be part of the exact problem we have as a world. People don't look at the world as a "whole". They just pick apart all the problems when in reality there is only "one". Are you a robot?

By the way. There is no such thing as algorithms for evolution. "We" are essentially the "algorithms" to evolution. You are not fully grasping the concept of what "learning" is. In this life you either "learn" or you "don't". You may "know" some things but that doesn't mean you've learned squat.

Last edited by TwoCoins; January 11th, 2017 at 08:41 AM.

January 11th, 2017, 09:31 AM   #15
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 1,791
Thanks: 576

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
 Originally Posted by TwoCoins You aren't understanding a word I say. I find this normal among the people stuck in the numbers. You are off in this algorithm world where everything is "suppose" to be exact. When things are only "exact" when correct.
Maths and physics theorems are well suited to deal with approximations, perturbations and other forms uncertainty... not everything is 'exact' or even well understood, but it is certainly well defined. Complexity classes in the same way are well defined so that the concepts can be clearly communicated.

I'd wager that the reason that you are finding that it is "normal among the people stuck in the numbers" to disagree with you is because those people are actually equipped with the knowledge to realize that what you are saying is silly or nonsense.

Also, something can be both precisely defined and incorrect. Take a look at the meaning of "accuracy" versus "precision" and sources of error. They typically apply to measurements, but those concepts are fairly general.

Quote:
 You are thinking in terms way to complicated. You pick apart my post like I was making different conjectures when actually the whole thing was one point.
It's actually very simple. Any argument is made by making a set number of logical steps that lead from one premise to another, leading to a conclusion (i.e. your point). The argument fails if any one of those steps is proved false or the argument becomes flimsy if the uncertainty around any one of those premises is great. In your case I am just commenting on why I think some of the things you say are silly with reasons why. I am picking apart the individual steps of your post (whether they are conjectures or not) that lead to your point, with explanations about each one.

Quote:
 This may be part of the exact problem we have as a world. People don't look at the world as a "whole". They just pick apart all the problems when in reality there is only "one". Are you a robot?

Quote:
 By the way. There is no such thing as algorithms for evolution. "We" are essentially the "algorithms" to evolution. You are not fully grasping the concept of what "learning" is. In this life you either "learn" or you "don't". You may "know" some things but that doesn't mean you've learned squat.
Wow. Apparently there's no such thing as algorithms for evolution and I am apparently not grasping what learning is. Well aren't you a lovely person!

Well, by the way, here's a link to a MATLAB implementation of a genetic algorithm, which is part of their global optimization toolbox:

https://uk.mathworks.com/discovery/g...algorithm.html

Here's some wikipedia articles about genetic algorithms and their applications, which you might find enlightening.

https://en.wikipedia.org/wiki/Genetic_algorithm
https://en.wikipedia.org/wiki/Evolutionary_algorithm

Numerical methods are my forte. I have helped two Masters students so far with their Masters theses on numerical models

Have fun!

Last edited by Benit13; January 11th, 2017 at 09:36 AM.

January 11th, 2017, 10:03 AM   #16
Newbie

Joined: Jan 2017
From: United States

Posts: 9
Thanks: 0

Quote:
I am not trying to be rude. The truth is the truth my friend.

Yes there is an "exact" of everything "yet" to be found or it has been found. Whether you realize this or not.

I didn't actually mean there is no algorithms to evolution. I meant more in the terms of the "bigger picture" as YOU are an "in the works algorithm" yourself solving foreign algorithms outside of your consciousness to in turn hopefully "learn" what your algorithm is.

Last edited by TwoCoins; January 11th, 2017 at 10:10 AM.

 Tags explanation, pnp

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post johnmath Math Books 6 January 27th, 2013 04:13 PM SedaKhold Calculus 0 February 13th, 2012 12:45 PM The Chaz Calculus 1 August 5th, 2011 09:03 PM katie0127 Advanced Statistics 0 December 3rd, 2008 02:54 PM Ujjwal Number Theory 2 September 29th, 2008 07:06 AM

 Contact - Home - Forums - Top