P versus NP Problem: Is P = NP?

P versus NP Problem: Is P = NP?

Postby Guest » Tue Jun 15, 2021 9:42 am

FYI: "P versus NP problem",

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

Is P = NP? "We do not know!" :(
Attachments
Euler diagram for P, NP, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete).png
Is P = NP? "We do not know!"
Euler diagram for P, NP, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete).png (5.5 KiB) Viewed 32864 times
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Tue Jun 15, 2021 11:25 am

Guest wrote:FYI: "P versus NP problem",

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

Is P = NP? "We do not know!" :(


Hah! The current state of affairs (Is P = NP? "We do not know!") is unacceptable! We can do better, and we will do better! :)

"We must know. We will know!" -- David Hilbert.
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Wed Jun 16, 2021 11:59 pm

"3. WHAT IF P = NP?

To understand the importance of the P versus NP problem
let us imagine a world where P = NP. Technically we could
have P = NP but not have practical algorithms for most
NP-complete problems. But suppose in fact that we do have
very quick algorithms for all these problems.

Many focus on the negative, that if P = NP then public-
key cryptography becomes impossible. True but what we
will gain from P = NP will make the whole internet look
like a footnote in history.

Since all the NP-complete optimization problems become
easy, everything will be much more efficient. Transporta-
tion of all forms will be scheduled optimally to move people
and goods around quicker and cheaper. Manufacturers can
improve their production to increase speed and create less
waste. And I'm just scratching the surface.

Learning becomes easy by using the principle of Occam's
razor{we simply nd the smallest program consistent with
the data. Near perfect vision recognition, language compre-
hension and translation and all other learning tasks become
trivial. We will also have much better predictions of weather
and earthquakes and other natural phenomenon.

P = NP would also have big implications in mathematics.
One could nd short fully logical proofs for theorems but
these fully logical proofs are usually extremely long. But we
can use the Occam razor principle to recognize and verify
mathematical proofs as typically written in journals. We
can then nd proofs of theorems that have reasonably length
proofs say in under 100 pages. A person who proves P =
NP would walk home from the Clay Institute, not with one
million-dollar check but with seven (actually six since the
Poincaré Conjecture appears solved).

Don't get your hopes up. Complexity theorists generally
believe P [tex]\ne[/tex] NP and such a beautiful world cannot exist."

Source Link: https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf.
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 19, 2021 5:50 pm

Hmm. We shall go against established
beliefs... We claim P = PN (The world is exceedly beautiful! Thank and praise Lord GOD! Amen!). And we claim our proof will be constructive and quite technical too.

Moreover, we expect a definitive proof, affirmative or negative, soon (within 12 months in honor/praise of Lord GOD. Amen!). :-)
Guest
 

P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 19, 2021 5:57 pm

Guest wrote:Hmm. We shall go against established
beliefs... We claim P = PN (The world is exceedly beautiful! Thank and praise Lord GOD! Amen!). And we claim our proof will be constructive and quite technical too.

Moreover, we expect a definitive proof, affirmative or negative, soon (within 12 months in honor/praise of Lord GOD. Amen!). :-)


... The world is exceedingly beautiful! ... Amen! :-)
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sun Jun 20, 2021 12:44 pm

Update wrote:Hmm. We shall go against established beliefs... We claim P = NP (The world is exceedingly beautiful! Thank and praise Lord GOD! Amen!). And we claim our proof will be constructive and quite technical too.

Moreover, we expect a definitive proof, affirmative or negative, soon (within 12 months in honor/praise of Lord GOD. Amen!). :-)


Good Luck!! :-)

P.S. P [tex]\ne[/tex] NP is the most likely outcome.
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Mon Jun 21, 2021 12:34 pm

FYI: 'Chapter 17: Limits to Computation' by Prof. C. A. Shaffer is quite good! Enjoy! :)

Source Link: https://people.cs.vt.edu/shaffer/Book/Java3e20110103.pdf.
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Mon Jun 21, 2021 2:39 pm

Guest wrote:FYI: 'Chapter 17: Limits to Computation' by Prof. C. A. Shaffer is quite good! Enjoy! :)

Source Link: https://people.cs.vt.edu/shaffer/Book/Java3e20110103.pdf.


Enough is enough... Let's solve our problem: Is P = NP?
Attachments
Silhouette of Sherlock Holmes.jpg
Is P = NP?
Silhouette of Sherlock Holmes.jpg (5.13 KiB) Viewed 32783 times
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Mon Jun 21, 2021 8:23 pm

Can we construct a polynomial-time algorithm that solves TSP (Travelling Salesman Problem)?

Reference Links: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity;

https://en.wikipedia.org/wiki/Time_complexity.
Attachments
Solution of a travelling salesman problem -- the black line shows the shortest possible loop that connects every red dot..png
Is P = NP?
Solution of a travelling salesman problem -- the black line shows the shortest possible loop that connects every red dot..png (7.92 KiB) Viewed 32777 times
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Fri Jun 25, 2021 7:18 pm

Guest wrote:Can we construct a polynomial-time algorithm that solves TSP (Travelling Salesman Problem)?

Reference Links: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity;

...


FYI: "At last! There’s an algorithm that’s closer than ever to solving the traveling salesperson problem." :)

https://thenextweb.com/news/at-last-theres-an-algorithm-thats-closer-than-ever-to-solving-the-traveling-salesperson-problem.
Attachments
This collection of dots and lines is the shortest traveling salesperson problem tour that passes through 1,000 points..png
Is P = NP?
This collection of dots and lines is the shortest traveling salesperson problem tour that passes through 1,000 points..png (817.79 KiB) Viewed 32750 times
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Fri Jun 25, 2021 7:37 pm

FYI: 'A (Slightly) Improved Approximation Algorithm for Metric TSP' by Profs. A. R. Karlin et al.,

https://arxiv.org/pdf/2007.01409.pdf. Good work! :)
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Fri Jun 25, 2021 10:49 pm

Guest wrote:FYI: 'A (Slightly) Improved Approximation Algorithm for Metric TSP' by Profs. A. R. Karlin et al.,

https://arxiv.org/pdf/2007.01409.pdf. Good work! :)


A Simple Reference Link: https://www.csd.uoc.gr/~hy583/papers/ch11.pdf
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 2:27 am

Guest wrote:
Guest wrote:Can we construct a polynomial-time algorithm that solves TSP (Travelling Salesman Problem)?

Reference Links: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity;

...


FYI: "At last! There’s an algorithm that’s closer than ever to solving the traveling salesperson problem." :)

https://thenextweb.com/news/at-last-theres-an-algorithm-thats-closer-than-ever-to-solving-the-traveling-salesperson-problem.



“Truth is ever to be found in simplicity, and not in the multiplicity and confusion of things.” -- Isaac Newton.
*****

“Imagination is more important than knowledge.“

“No problem can be solved from the same level of consciousness that created it.“
-- Albert Einstein.
*****

A Proposed Solution for TSP (Travelling Salesman Problem)

Hmm. We need to be imaginative/inventive to solve TSP in polynomial time or less (a very unlikely possibility)...

Let's imagine our undirected weighted graph (unsolved TSP) as a complex electrical circuit (a combination of series and quasi-parallel connected branches) with connected wires, light bulbs, and measuring sensors (voltage/load meters).

Each node (vertex) of our circuit has one or more light bulbs attached to it that indicate the number of branches connected to it. And only a matching voltage or higher applied to each branch that corresponds to a given value (refer to our TSP graph for the assigned values) will turn a corresponding light bulb on.

The computed overall average value (average voltage applied to the circuit) of all branch values will turn on more or less half(a rough estimate) of all lights of our imagined circuit.

We need to compute the average value of all branch values higher than the overall average voltage for our circuit too.

We apply that higher average voltage to our circuit and gradually increase the voltage until all lights of the circuit is turned on. Next, we measure the voltages of all appropriate branches of the circuit, and we compute any difference between assigned values and the measured values...

TSP is solved! Wow!

We further claim TSP can be solved in polynomial time or less time! Wow! :D

P.S. Is P = NP? Yes! :D
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 3:05 am

Remark: Hmm. If our reasoning for the previous post is correct, we should be able to formulate a polynomial-time algorithm that solves TSP. :)
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 3:52 am

Guest wrote:Remark: Hmm. If our reasoning for the previous post is correct, we should be able to formulate a polynomial-time algorithm that solves TSP. :)


Remark: Discernment, testing, and some ingenuity will solve TSP in polynomial time. We are now confident it can be done. Good Luck! :D
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 4:45 am

Update:

"...We apply that higher average voltage to our circuit and gradually increase or decrease the voltage until all appropriate light bulbs of the circuit are turned on. Next, we measure the voltages of all appropriate branches of the circuit, and we compute any difference between assigned values and the measured values..."

Remark: Appropriate branches may be a hard part of our problem...
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 2:26 pm

Our posts were deleted... Why?
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 2:36 pm

Update: (Please do not delete. Thank you!)

“Truth is ever to be found in simplicity, and not in the multiplicity and confusion of things.” -- Isaac Newton.
*****

“Imagination is more important than knowledge.“

“No problem can be solved from the same level of consciousness that created it.“
-- Albert Einstein.
*****

A Proposed Solution for TSP (Travelling Salesman Problem):

Hmm. We need to be imaginative/inventive to solve TSP in polynomial time or less (a very unlikely possibility)...

Let's imagine our undirected weighted graph (unsolved TSP) as a complex electrical circuit (a combination of series and quasi-parallel connected branches) with connected wires, light bulbs, and measuring sensors (voltage/load meters).

Each node (vertex) of our circuit has one or more light bulbs attached to it that indicate the number of branches connected to it. And only a matching voltage or higher applied to each branch that corresponds to a given value (refer to our TSP graph for the assigned values) will turn a corresponding light bulb on.


The computed overall average value (average voltage applied to the circuit) of all branch values will turn on more or less half(a rough estimate) of all light bulbs of our imagined circuit.

We need to compute the average value of all branch values higher than the overall average voltage for our circuit too.

We apply that higher average voltage to our circuit and gradually increase or decrease the voltage until all appropriate light bulbs of the circuit is turned on. Next, we measure the voltages of all appropriate branches of the circuit, and we compute any difference between assigned values and the measured values...

TSP is solved! Wow!

Remark: Appropriate indicates the required amount needed to solve TSP optimally. We do not want to turn on all lights of our circuit...

We further claim TSP can be solved in polynomial time or less time! Wow! :D

P.S. Is P = NP? Yes! :D
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 2:42 pm

Minor Update for Previous Post:

"We apply that higher average voltage to our circuit and gradually increase or decrease the voltage until all appropriate light bulbs of the circuit are turned on. Next, we measure the voltages of all appropriate branches of the circuit, and we compute any difference between assigned values and the measured values..."
Guest
 

Re: P versus NP Problem: Is P = NP?

Postby Guest » Sat Jun 26, 2021 5:08 pm

Remark: (Please do not delete. Thank you!) We are very confident that we can construct a polynomial-time algorithm that solves TSP optimally!

Thank Lord GOD! Amen! :D

P.S. Go Blue! :D
Guest
 

Next

Return to Number Theory



Who is online

Users browsing this forum: No registered users and 6 guests