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 14 70.00% Wrong 6 30.00% Voters: 20. You may not vote on this poll

 January 5th, 2017, 09:52 AM #1 Newbie   Joined: Jan 2017 From: United States Posts: 9 Thanks: 0 My "P=NP" Explanation 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. 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. Solving the problem would make it correct/solved. If you can easily check the problem is correct then you have solved the problem. 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.
 January 5th, 2017, 10:45 AM #2 Senior Member   Joined: Sep 2016 From: USA Posts: 114 Thanks: 44 Math Focus: Dynamical systems, analytic function theory, numerics 1. You are replacing the true conjecture by a helpful intuitive device. Namely, you have glossed over what "easy" means when the actual conjecture has a very precise notion of this (polynomial time solver <-----> polynomial time checker). While it is nice to use metaphor to explain difficult concepts to people who aren't familiar with some of the technicalities, do not mistake a solution of the metaphorical problem with a solution of the actual problem. 2. You are incorrect that being able to easily check a solution implies you "know" the solution. That is the entire point. Here we are discussing algorithms for solving a problem vs algorithms for checking a solution. As an example consider the equation $x^y = y^x$. It is trivial to verify that $(2,2)$ is a solution. Are there others? If so how would you find them? Thanks from Benit13
 January 5th, 2017, 12:47 PM #3 Newbie   Joined: Jan 2017 From: United States Posts: 9 Thanks: 0 You would find them by trial and error just like you find algorithms. Some more complex than others.
 January 5th, 2017, 01:20 PM #4 Senior Member   Joined: Aug 2012 Posts: 1,264 Thanks: 296 Here's a 119 page paper by computer scientist and blogger Scott Aaronson on the state of the art on this problem. http://www.scottaaronson.com/papers/pnp.pdf Thanks from Benit13
January 5th, 2017, 03:43 PM   #5
Senior Member

Joined: Sep 2016
From: USA

Posts: 114
Thanks: 44

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by TwoCoins You would find them by trial and error just like you find algorithms. Some more complex than others.
Sure this works great. In my example you would have to exhaust the continuum to use trial and error to solve $x^y = y^x$. I'm not even sure how one talks about exhausting the continuum but I'm betting its not a polynomial time algorithm.

As a less absurd example, factoring is believed by many to be NP-complete (or worse). Moreover, there exist plenty of algorithms for solving this problem. For example, the most naive approach is called trial division and it factors $N \in \mathbb{N}$ by simply computing the GCD of $(p,N$ for every prime $p < \sqrt{N}$. The point is, the runtime of this algorithm is not bounded by any polynomial in the size of the input (in this case $\log N$).

This is where the importance of mathematically precise statements becomes relevant. There are algorithms for solving any NP-complete problem you can think of. They are just all "slow" with respect to the statement of the conjecture.

 January 9th, 2017, 07:35 AM #6 Newbie   Joined: Jan 2017 From: United States Posts: 9 Thanks: 0 I still stand by my conclusion. Somebody prove my conclusion wrong?
 January 9th, 2017, 07:39 AM #7 Newbie   Joined: Jan 2017 From: United States Posts: 9 Thanks: 0 My conclusion: The solution is only easy once you find the "exact problem" and solve it "correctly". Until then its "not easy". It's that simple folks.
January 9th, 2017, 07:45 AM   #8
Newbie

Joined: Jan 2017
From: United States

Posts: 9
Thanks: 0

Quote:
 Originally Posted by SDK Sure this works great. In my example you would have to exhaust the continuum to use trial and error to solve $x^y = y^x$. I'm not even sure how one talks about exhausting the continuum but I'm betting its not a polynomial time algorithm. As a less absurd example, factoring is believed by many to be NP-complete (or worse). Moreover, there exist plenty of algorithms for solving this problem. For example, the most naive approach is called trial division and it factors $N \in \mathbb{N}$ by simply computing the GCD of $(p,N$ for every prime $p < \sqrt{N}$. The point is, the runtime of this algorithm is not bounded by any polynomial in the size of the input (in this case $\log N$). This is where the importance of mathematically precise statements becomes relevant. There are algorithms for solving any NP-complete problem you can think of. They are just all "slow" with respect to the statement of the conjecture.
I love how you explain everything here. But the "continuum" you speak of cannot be exhausted or never will be "exhausted". Problems are a constant. I still stand by my answer good sir.

 January 9th, 2017, 08:35 AM #9 Newbie   Joined: Jan 2017 From: United States Posts: 9 Thanks: 0 What I'm trying to say goes far beyond just that of math and numbers. When I am speaking of my conclusion I am speaking universally about my conclusion involving every problem you can think of and imagine. The continuum we live in is infinite. Thus the continuum cannot ever be exhausted and every problem that exists or can exist will not be figured out until solved correctly once and even then more problems keep on developing ( especially when we take a look at the infinity in numbers). New variables = New problems. Everything is infinite. If Joe Genius at Yale thinks he can crack this code with a "set" of numbers then I don't even know what I'm doing on this planet. lmao
January 9th, 2017, 09:45 AM   #10
Senior Member

Joined: Jun 2014
From: USA

Posts: 250
Thanks: 12

Quote:
 Originally Posted by TwoCoins What I'm trying to say goes far beyond just that of math and numbers. When I am speaking of my conclusion I am speaking universally about my conclusion involving every problem you can think of and imagine. The continuum we live in is infinite. Thus the continuum cannot ever be exhausted and every problem that exists or can exist will not be figured out until solved correctly once and even then more problems keep on developing ( especially when we take a look at the infinity in numbers). New variables = New problems. Everything is infinite. If Joe Genius at Yale thinks he can crack this code with a "set" of numbers then I don't even know what I'm doing on this planet. lmao
A problem that can be solved in polynomial time is within the class of problems P. A problem that has a solution that can be verified in polynomial time is within the class of problems NP. The question is whether or not P = NP.

There are a set of problems that are considered NP complete. These are the problems being addressed, not "every problem you can think of and imagine" as you put it. You should look up what it means to be NP complete.

https://en.wikipedia.org/wiki/P_versus_NP_problem

"NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. ... The first natural problem proven to be NP-complete was the Boolean satisfiability problem. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, proof by reduction provided a simpler way to show that many other problems are also NP-complete, including the subset sum problem discussed earlier."

The subset sum problem is a great example:

Does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? If I give you a solution, {-2, -3, -10, 15}, you can check that solution in quickly (make three additions). If you don't know the solution, then you can program a computer to compute all possible subsets, perform the required addition, and see if a solution exists. The program doing this would have to compute $2^n-n-1$ (2^n for all possible subsets, less n for all the singletons that do not have to be computed, less 1 for nullset), different subsets, so it runs in exponential time as opposed to polynomial time.

To prove P = NP, you'd have to find a computer algorithm capable of finding a solution to the above subset sum problem in polynomial time as opposed to exponential time.

Personally, I think P $\neq$ NP, but who knows.

 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 - Cryptocurrency Forum - Top