News for hackers. Stuff that matters.
Re:The Scientific Case for P≠NP by SomeStupidPoint on Sunday October 29, 2017 @11:43AM (#15579695)
My point is that his heuristic has dropped my expected value for betting on P != NP, because his argument is one that suggests we will find a class, not that we won't.

His description of "passing tests" actually sounds like the buildup of stress before breakage, where many near-faults are generated.

I'm less confident of the resolution post reading that -- so it seems extremely weird to present as evidence that P != NP, as it shifted my beliefs the exact opposite way.

Re:The Scientific Case for P≠NP by naasking on Sunday October 29, 2017 @12:01PM (#15579788)
Then perhaps you haven't properly understood the argument he's making. Your "stress before breakage" argument is literally the gambler's fallacy.
Re:The Scientific Case for P≠NP by SomeStupidPoint on Sunday October 29, 2017 @12:06PM (#15579804)
> Your "stress before breakage" argument is literally the gambler's fallacy.

It's not even anything close: the gambler's fallacy requires that the events you're trying to relate are uncorrelated.

The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions.

So -- the fallacy requires you be trying to correlate uncorrelated things; I am not. I'm correlating things that are going to be correlated because of how the spaces are constructed.

Re:The Scientific Case for P≠NP by naasking on Monday October 30, 2017 @02:09PM (#15587410)
> The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions.

Is it? This strikes me as pretty contentious.

Re:The Scientific Case for P≠NP by SomeStupidPoint on Monday October 30, 2017 @05:12PM (#15588950)
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.

Re:The Scientific Case for P≠NP by rocqua on Monday October 30, 2017 @05:50PM (#15589235)
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.

Re:The Scientific Case for P≠NP by SomeStupidPoint on Monday October 30, 2017 @08:32PM (#15590245)
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".

Re:The Scientific Case for P≠NP by rocqua on Wednesday November 01, 2017 @06:26PM (#15606063)
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.