Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to P vs. NP

wesammikhail.com

Post reply on HN
Print view View original

11–20 of 41 posts

Re: Introduction to P vs. NP

#11

Post by harles »

xref wrote: post #10

> Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain Wish they’d given/linked a few examples there, anyone happen to know some off the top of their head?

Not a recent example, but the Ellipsoid Method[0] is a famous example of this. It took a class of problems (Linear Programs) from NP to P in 1979 but was completely impractical (I want to say something like N^6). It has an interesting history worth a read - it was also a big USSR contribution to the field, which there weren’t many of at the time.

[0]: https://en.m.wikipedia.org/wiki/Ellipsoid_method

Re: Introduction to P vs. NP

#12

Post by xref »

harles wrote: post #11
xref wrote: post #10

> Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain Wish they’d given/linked a few examples there, anyone happen to know some off the top of their head?

Not a recent example, but the Ellipsoid Method[0] is a famous example of this. It took a class of problems (Linear Programs) from NP to P in 1979 but was completely impractical (I want to say something like N^6). It has an interesting history worth a read - it was also a big USSR contribution to the field, which there weren’t many of at the time. [0]: https://en.m.wikipedia.org/wiki/Ellipsoid_method

Oh wow thanks, this is definitely sending me down a Wikipedia rabbit hole; the Ellipsoid method was improved upon via Karmarkar’s algorithm in 1984. Also nicely illustrates that a problem which moves from NP to P can still be moved even further into P-territory

_also_ Karmarkar’s algo appears to be an important law case on whether math can be copyrighted for people interested in that angle

https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm

Re: Introduction to P vs. NP

#13

Post by JohnKemeny »

xref wrote: post #10

> Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain Wish they’d given/linked a few examples there, anyone happen to know some off the top of their head?

PRIMES, checking whether a number is a prime number or not.

It's important to note that this happens literally all the time in research. There are hundreds of problems that are easily seen to be _in NP_, that we simply don't know whether or not is in P. Many of these problems aren't that interesting, though.

Re: Introduction to P vs. NP

#14

Post by andersentobias »

chx wrote: post #9

One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one. This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate numb…

You don't need to involve a P vs NP discussion at all if you want to have a practical discussion to begin with. Big-Oh is sufficient?

Re: Introduction to P vs. NP

#15

Post by enriquto »

chx wrote: post #9

One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one. This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate numb…

Yes, the class P is huge. Calling problems in P "easy" is severely misguided. We have only barely scratched the surface of this class (linear and quadratic problems), but there is an infinitely deep ocean of problems below the surface that we cannot even imagine. It is illuminating to recall Knuth's view that probably P=NP, but it won't have any practical effect.

Re: Introduction to P vs. NP

#16

Post by tromp »

> P is a class of problems that are easy to solve and easy to verify.

> NP, on the other hand, is a class of problems that are hard to solve yet easy to verify.

The latter description is not quite correct, as NP includes P. So not all problems in NP are hard to solve. Similarly with EXP.

The class of problems that are hard to solve yet easy to verify, is exactly NP\P, which we assume (but cannot prove) is non-empty.

Re: Introduction to P vs. NP

#19

Post by quickthrower2 »

andersentobias wrote: post #14
chx wrote: post #9

One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one. This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate numb…

You don't need to involve a P vs NP discussion at all if you want to have a practical discussion to begin with. Big-Oh is sufficient?

Profiling the code with different size inputs is sufficient

Re: Introduction to P vs. NP

#20

Post by alberto_ol »

ChancyChance wrote: post #8
chippiewill wrote: post #2

I feel like this is a pretty bad introduction to P vs NP., no? It doesn't ever actually even begin to explain what P and NP are, only what their vague properties are.

I thought it was helpful. Got a better link?

This article for non-specialists is longer and more technical, but I found it interesting:

https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW0...

Post reply on HN