You are viewing a single comment's thread from:

RE: The P vs. NP Problem

in #steemstem7 years ago (edited)

This statement is a bit incomplete: There is one misconception though, even if we managed to prove that P=NP, we still have to develop the algorithms for NP problems. The point of NP-completeness is that if you can show that there exists a NP-complete problem which is also P then you have shown that NP=P. By doing this you will have found a method to solve all NP problems in polynomial time (by the definition of NP completeness).


DQmWPdXSwgcwQV5uuTRybUZH3vUZ6pTw4ESZmDT7Ey7DXbW_1680x8400.png

Sort:  

Yes indeed. That's the whole point of NP-completeness. I was thinking of non-constructive proofs. I mean Polynomial time doesn't necessarily mean it will be quick. If someone comes up with, say O(n100), that wouldn't be practical. But I clearly messed up.

I made the correction. Thanks for the feedback!

Coin Marketplace

STEEM 0.21
TRX 0.26
JST 0.040
BTC 100671.43
ETH 3655.73
USDT 1.00
SBD 3.14