My Math Forum  

Go Back   My Math Forum > Math Forums > Math

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

Thanks Tree3Thanks
Reply
 
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.
TwoCoins is offline  
 
January 5th, 2017, 09:45 AM   #2
SDK
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?
Thanks from Benit13 and RalphD
SDK is offline  
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.
TwoCoins is offline  
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
Thanks from Benit13
Maschke is offline  
January 5th, 2017, 02:43 PM   #5
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 167
Thanks: 77

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
Originally Posted by TwoCoins View Post
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.
SDK is offline  
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?
TwoCoins is offline  
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.
TwoCoins is offline  
January 9th, 2017, 06:45 AM   #8
Newbie
 
Joined: Jan 2017
From: United States

Posts: 9
Thanks: 0

Quote:
Originally Posted by SDK View Post
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.
TwoCoins is offline  
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
TwoCoins is offline  
January 9th, 2017, 08:45 AM   #10
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by TwoCoins View Post
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.
AplanisTophet is offline  
Reply

  My Math Forum > Math Forums > Math

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 exeriment-need help finding "statistic" and "result" katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM
terms "non-increasing" or "non-decreasing" Ujjwal Number Theory 2 September 29th, 2008 07:06 AM





Copyright © 2017 My Math Forum. All rights reserved.