
Math General Math Forum  For general math related discussion and news 
View Poll Results: Am I wrong or Simply Correct?  
Simply Correct  23  69.70%  
Wrong  10  30.30%  
Voters: 33. You may not vote on this poll 
 LinkBack  Thread Tools  Display Modes 
January 5th, 2017, 08: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, 09:45 AM  #2 
Senior Member Joined: Sep 2016 From: USA Posts: 167 Thanks: 77 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? 
January 5th, 2017, 11:47 AM  #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, 12:20 PM  #4 
Senior Member Joined: Aug 2012 Posts: 1,569 Thanks: 379 
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 
January 5th, 2017, 02:43 PM  #5  
Senior Member Joined: Sep 2016 From: USA Posts: 167 Thanks: 77 Math Focus: Dynamical systems, analytic function theory, numerics  Quote:
As a less absurd example, factoring is believed by many to be NPcomplete (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 NPcomplete problem you can think of. They are just all "slow" with respect to the statement of the conjecture.  
January 9th, 2017, 06: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, 06: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, 06:45 AM  #8  
Newbie Joined: Jan 2017 From: United States Posts: 9 Thanks: 0  Quote:
 
January 9th, 2017, 07: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, 08:45 AM  #10  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
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 "NPcomplete problems are a set of problems to each of which any other NPproblem 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 NPcomplete problems. ... The first natural problem proven to be NPcomplete was the Boolean satisfiability problem. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NPcomplete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NPcomplete, proof by reduction provided a simpler way to show that many other problems are also NPcomplete, 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^nn1$ (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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Can anyone help me finding this book "Evariste Galois "Toti"  johnmath  Math Books  6  January 27th, 2013 03:13 PM 
A "simple" application of dirac delta "shift theorem"...help  SedaKhold  Calculus  0  February 13th, 2012 11:45 AM 
"separate and integrate" or "Orangutang method"  The Chaz  Calculus  1  August 5th, 2011 09:03 PM 
sample exerimentneed help finding "statistic" and "result"  katie0127  Advanced Statistics  0  December 3rd, 2008 01:54 PM 
terms "nonincreasing" or "nondecreasing"  Ujjwal  Number Theory  2  September 29th, 2008 07:06 AM 