Comment by SomeStupidPoint | Hacker News Reader

Comment by SomeStupidPoint | Hacker News Reader

Parent Full thread

SomeStupidPoint

How so?

Clearly there's a reason you think that isn't true -- perhaps you could share it instead of hiding behind just calling it "contentious".

It seems the stronger claim to suppose that the lower dimensions are rough and the top are smooth, especially when you think about where that roughness comes from.

Let's imagine a class "UP" which is the useful polynomial algorithms -- things we might actually compute.

The arguments raised here are a heuristic that UP != NP, which it certainly supports. My objection is that not only does that argument for UP != NP not support P != NP, it actually is evidence for P = NP, because UP seems to get asymtotically close to NP, and we know there are portions of P outside of UP -- suggesting we can find a "high" P region that sits atop UP and gets nudged over the line as UP approaches NP.

The suggestion that UP approaches NP but there's no P that crosses bears some supporting. Our disagreement seems to be over the obviousness of that relationship, and how much UP resembles P as a whole.

If all shots from storm troopers seem to barely miss, does that indicate that eventually we a storm trooper will miss? Or does it indicate a conspiracy among storm troopers to miss.

There are (apparantely) so many near misses for which it isn't clear why it should be a near miss. A great explanation for this near missing is the underlying fact that all NP problems contain some 'brute force' core that can never be polynomial.

Also note that the blog post does not at all concern your class UP. None of these are algorithms designed to be run. They are all about exploring abstract complexity classes.

My point is stormtroopers:empire::UP:P

You're correct that stormtroopers will never hit, wrong that stormtroopers are representative of the empire, and wrong about the correlation between stormtrooper hits and empire hits, because you're ignoring higher order effects (eg, while stormtroopers always miss, the empire must hit something to be the "bad guy" -- and they do: Luke's parents, Alderaan, Obi-Wan, Hoth, Luke's arm, etc.

But purely from the existence of stormtroopers consistently missing, you can infer there's a Darth Vader that must score some hits, or the plot wouldn't work. I think we might be in a similar case for P ?= NP, and you're all way too blasse predicting from stormtroopers.

Very little research has been done on P - UP, where UP is all polynomials with degree less than 10,000 and coefficients less than 10^100.

In fact, I don't know a single P-UP algorithm that wasn't explicitly constructed to be -- do you?

I just think most of us are subtly talking about UP, not P. (Including the blog post.) And that you've incorrectly inferred a "plot" when all you've observed is "redshirt fire".

UP is much harder to deal with for a very simple reason. Composition of polynomials is still polynomial. Composition of polynomials of low degree leads to polynomials with high degree.

You keep assuming we only look at UP, whereas actually our theoretical work explicitly looks at P. Often, we don't even care about actual efficiency of the algorithm. The constants might be astronomical, but we still like the algorithm for its asymptotic properties.

I'm not versed in recent research, but I imagine the composition argument above often leads to polynomial performance with stupid degrees. I expect people only compute the actual degree when they thing it might be low.

Again though, this is not my field of research.

Reply on news.ycombinator.com