[HN Gopher] What P vs. NP is about
___________________________________________________________________
What P vs. NP is about
Author : signa11
Score : 80 points
Date : 2024-10-02 05:46 UTC (3 days ago)
(HTM) web link (vasekrozhon.wordpress.com)
(TXT) w3m dump (vasekrozhon.wordpress.com)
| vouaobrasil wrote:
| > We recently made a Polylog video about the P vs NP problem. As
| usual, our goal was to present an underrated topic in a broadly
| understandable way
|
| Interesting post but not sure why the author calls it underrated.
| It seems to get a fare share of attention and love amongst those
| that care about such things.
| karmakurtisaani wrote:
| It's hardly an underrated topic. In fact, probably the most
| well-known from all the millennium prize problems.
|
| Edit: presenting the problem with inverting functions is an
| unusual approach tho.
| theturtletalks wrote:
| I was introduced to the P vs. NP problem via the traveling
| salesman problem and honestly seems like easiest way to
| explain it to people.
| vlovich123 wrote:
| Interestingly the shortest route question of the salesman
| problem (which is what everyone associates it with) is NP-
| hard and thus not necessarily even within NP. P vs NP is
| specifically about P vs NP complete whereas NP-hard is
| problems that are at least as hard as NP-complete but need
| not be in NP nor decision problems. So make sure you give
| the "is there a route <= k" version because the much more
| common "find the shortest route version" is not NP.
|
| https://stackoverflow.com/questions/1857244/what-are-the-
| dif...
|
| https://en.m.wikipedia.org/wiki/Travelling_salesman_problem
| pyrale wrote:
| In this case np-complete and np-hard are closely linked:
| the optimization problem can be reduced to the decision
| version. Not all decision problems are like that (e.g.
| happy net problem), but for this one I don't see the
| point making the distinction.
| alex_smart wrote:
| To whatever extent the shortest route question is not in
| NP, it is also not NP-hard.
|
| Both NP and NP-hard are defined for the class of decision
| problems.
| krick wrote:
| Somebody really should come up with better names. I know
| for a fact I knew the difference once, but right now I
| cannot even remember what it was without clicking the
| link. Surely many people who heard about this problem
| (and that's a lot of people, it's about as pop-mathy as
| it gets) don't even suspect these aren't synonymous.
| KPGv2 wrote:
| Personally, I think it's fair to say all Millennium Prize
| problems are underrated because 99.9% of humans alive have no
| idea what that is.
| karmakurtisaani wrote:
| Well, better start making some more YouTube videos then.
| gosub100 wrote:
| I think that word is in the process of being re-defined. I see
| it used a lot in the context of older pop music or
| singers/bands that are no longer at their peak.
|
| My own pet theory is that it's an evolution of speech towards
| "hardened" claims that you can't easily disagree with. You
| cannot disagree with "over/under-rated" because there's no
| official "rating" method. You cannot disagree with "vibes"
| because the source of a vibration is impossible to determine.
| They both allow a speaker to make a claim without evidence.
| tgv wrote:
| Might be the clickbait treadmill, indeed, or algospeak. But
| it doesn't need an objective meaning to be treated that way.
| The word "literally" can no longer be trusted to mean "in a
| literal sense". It's frequently used as an intensifier.
| magicalhippo wrote:
| Yeah was gonna say the same. As seen on a recent video:
| "Blondie is so underrated!"...
|
| Though I guess for a lot of young people it feels like that,
| with none of their friends talking about such bands.
| munchler wrote:
| Framing this as inverting a function is interesting, but raises a
| question, since any function that maps multiple inputs to the
| same output is not invertible.
|
| For example, let's say we invert a checker algorithm and "run it
| backward from YES". Does that find an arbitrary single solution?
| Does it find all solutions? What if there are an infinite number
| of solutions?
| LegionMammal978 wrote:
| "An arbitrary single solution" would be the proper answer for
| NP. The goal is to find _some_ solution that the verifier
| accepts, like how in SAT the goal is to find _some_ satisfying
| assignment for all clauses.
| delusional wrote:
| Given that there is potentially an exponential number of
| solutions, it would be impossible to enumerate them all in
| anything smaller than exponential time.
| cvoss wrote:
| In some contexts, the inverse of a function f : A -> B is
| defined as a function g : B -> A such that g(f(x)) = x and
| f(g(y)) = y for all x,y.
|
| In other contexts, what is meant is g : B -> 2^A such that x is
| in g(f(x)) for all x and f(x') = f(x) for all x' in g(f(x)).
| Here, g is said to produce the pre-image under f, and is a
| generalization of the above definition of inverse for non-
| injective functions.
|
| In other contexts still, what is meant is g : B -> A such that
| f(g(y)) = y for all y such that there exists some x with f(x) =
| y. This is a different generalization called a one-sided
| inverse. (People probably call it a left inverse or right
| inverse, but I can never remember which is which because it
| emerges from an arbitrary notational convention.)
|
| The article uses inverse in this third sense. "Find some input
| to f which would yield a given output y, if one exists."
| analog31 wrote:
| Informally, an example of this problem is calculus class. A kid
| who's interested in programming, and takes calculus, can dream
| up a program that computes the derivative of any expression.
| But now try doing that with the anti-derivative. And to be sure
| you can write an expression in multiple ways, but the core
| problem remains.
|
| Disclosure: I was that kid. My program was a mess, but good
| enough for a proof of concept.
| afiodorov wrote:
| Idea is to add enough constraints to the function so that
| inverting it is non trivial (where inverts finds ANY input).
| Like the video said inverting multiplication with the output of
| 15 could yield 15 = 15 * 1, so just make the function f(a, b) =
| a * b where a > 1 and b > 1 for a more interesting RSA-breaking
| case.
| nick_g wrote:
| Despite being mentioned throughout the post, I don't see a link
| to the video in question. I saw it when it was posted a few weeks
| back and really enjoyed it. I would highly recommend giving it a
| watch, especially if the ramifications of P vs NP are new to you
| [1]
|
| [1] https://www.youtube.com/watch?v=6OPsH8PK7xM
| Pikamander2 wrote:
| I've never understood why this problem is considered so
| difficult. I'm not a fancy schmancy computer scientist but even I
| can see that N = 1 or P = 0.
| HappMacDonald wrote:
| > even I can see that N = 1 or P = 0
|
| wat?
| Dylan16807 wrote:
| It's a joke, they're doing algebra on the letters.
| acchow wrote:
| I would recommend reading the article.
|
| P vs NP is one of the foundational open problems in computer
| science.
| kens wrote:
| I wasn't expecting to see my (uncredited) die photo of the 8008
| processor in the middle of an article about P vs NP!
| pipes wrote:
| BBC "in our time" radio show did an outstanding episode on the
| topic. As usual it had an amazing calibre of guests but a totally
| understated style. Also no long pointless intro full of terrible
| banter or lengthy bullet list of what will be discussed. I wish
| podcasts could follow this example:
|
| https://www.bbc.co.uk/programmes/b06mtms8
| antoine-levitt wrote:
| I just skimmed the article and didn't watch the video, but the
| bit about backpropagation is just wrong. Backpropagation doesn't
| compute an inverse of the jacobian, it computes its transpose.
| (although a similar idea to backpropagation could possibly be
| used to compute an inverse of several reversible layers, but
| that's not typically how neural networks work)
| usednoise4sale wrote:
| I know no one will believe this but I'm reasonably sure I proved
| P!=NP earlier this week.
|
| It was very similar to a previous unsolved problem in a "haha,
| history repeats itself" sort of way.
|
| This comment might have a lot more comments someday.
| OrigamiPastrami wrote:
| I don't believe you, but you can always prove me wrong and
| share your proof.
| usednoise4sale wrote:
| Well, it was recent, so I'm currently in the 'feedback and
| validation' stage. I've reached out to experts for feedback,
| but these things do take time.
|
| If you have a genuine interest, and especially if you could
| provide feedback or warm introductions to someone who can,
| I'm happy to share.
|
| You can email me at atmanthedog at Google's free email
| service domain. Put something HN related in the subject. *If
| you do, please share your mathematical background so I can
| better tailor a response.
| geysersam wrote:
| "I have discovered a truly marvelous demonstration of the
| proposition that P/=NP but this HN comment is too short to
| contain it..."
|
| Eagerly awaiting your published proof
| variadix wrote:
| Is the interesting part of P vs NP (since it seems very unlikely
| that P = NP) the mathematical machinery that would be required to
| prove that P != NP? Presumably doing so would require a way to
| determine a lower bound for _all_ possible algorithms that solve
| a particular problem.
___________________________________________________________________
(page generated 2024-10-05 23:00 UTC)