Hacker News: mockerell

New comment by mockerell in "NP-overrated"

mockerell — Fri, 14 Aug 2026 07:07:18 +0000

A personal favorite of mine is fixed-parameter tractability. Instead of analysing the worst case running time solely on the input length we introduce a *parameter* and study the time complexity in both. Intuitively, the parameter „should“ be small and is often chosen to be the solution size or some specific measure of the input.

Consider the vertex cover problem where you want to cover all edges of a graph by at most k vertices (that are incident to all edges). It is a classical NP-complete problem and the naive bruteforce solver needs something like n^k time. Which is already huge for small k, say, 10.

A very simple fixed-parameter tractable (fpt) algorithm for this problem achieves a worst case time of 2^k * n. For huge graphs and small k (again, let’s say 10) this is a massive improvement.

This is a very active field, where we have a good understanding which problems allow have such a worst case time and which not (under some complexity theoretic assumptions of course). It incorporates also the idea of restricting the input to only specific „simple“ instances gradually. This happens if you add graph measures as a parameter.

Many NP-hard graph problems are in P if restricted to planar graphs. But what if the instances are „almost“ planar? If you choose a parameter that measures the structure of a graph such that the measure is low if the graph is planar and high if it isn’t, any fpt algorithm for this parameterization works on any graph; fast if it is planar, and fast-ish if it is close to being planar.

Of course, this is theory with the similar metaphysical caveats classical complexity theorem has. However, it results in interesting algorithmcsl tools and interacts nicely with specific fields of structural graph theory.

New comment by mockerell in "NP-overrated"

mockerell — Fri, 14 Aug 2026 06:53:38 +0000

It is indeed very interesting. For the latter the concepts from fine-grained complexity and average time are interesting. For specific problems, there are theoretical fine grained lower bounds for time complexity (i.e. cannot be solved in (truly) subcubic time). However, these rely on assumptions that are even stronger than P != NP.

New comment by mockerell in "NP-overrated"

mockerell — Fri, 14 Aug 2026 06:50:25 +0000

You’re right, it doesn’t. However, in TSP you are allowed to visit each vertex *exactly* once. So traversing the minimum spanning tree naively is not a valid solution. What you the approximation does is to „shortcut“ the paths if you would revisit an already seen vertex again. That’s where you need the triangle inequality to guarantee that the shortcut isn’t longer than the path through the minimum spanning tree. Otherwise you cannot guarantee an approximation ratio of at most 2.

Nerd culture is murdering intellectuals

mockerell — Sun, 02 Aug 2026 07:57:52 +0000

Article URL: https://www.theintrinsicperspective.com/p/nerd-culture-is-murdering-intellectuals

Comments URL: https://news.ycombinator.com/item?id=49142128

Points: 54

# Comments: 71

New comment by mockerell in "AI in mathematics is forcing big questions"

mockerell — Sat, 27 Jun 2026 06:00:14 +0000

That’s an interesting way to think about it. While tests don’t satisfy mathematicians‘ standards for rigor one could instead look at interactive proofs from complexity theory. These are of interest if a problem doesn’t allow for short proofs, i.e. when the problem is not in NP [1]. In your scenario an adapted AI-assisted theorem prover would be the prover, and a mathematician the verifier.

[1] https://en.wikipedia.org/wiki/Interactive_proof_system

New comment by mockerell in "DHL Set to Transport Goods on New Wind-Powered Cargo Ships"

mockerell — Mon, 22 Jun 2026 16:09:19 +0000

Look no further! SailGP is pretty much the maritime version of F1

New comment by mockerell in "Never Give Them Your Face"

mockerell — Mon, 22 Jun 2026 15:44:12 +0000

I just wanted to tell you that I wholeheartedly agree with your statement and that you shouldn’t be discouraged by some of the nay-sayers in the replies. I feel that HN has many users who are techno-optimist, but are very pessimistic of the role of individuals and the possibilities of the society overall.

Even in the replies someone tries to appeal to some ideal of „rationalism“ which is nothing but defeatism to the status quo. They see any kind of passion, emotion or values as „irrational“ and categorically as something lesser.

But what is reason without values? Logic without axioms? Just treading in the trivial waters.

New comment by mockerell in "On Labubu and the Hyperreal"

mockerell — Wed, 27 May 2026 21:14:31 +0000

The lack of actual photos of Labubus "in the real" (usually on a keychain at a pant's belt loops) is jarring. The topic of the "performative male" has been regurgitated in social media for quite some time. Still the author ignores that and misses the overall bigger picture.

I think any argument made here with regard to Baudrillard's hyperreality could be made about most trends, not only Labubus. Actual insight into the demographic is missing.

I prefer the following video which touches on the performative male (it's in German though). Don't get distracted by the title, it's nuanced and offered me some insight into performative behaviors (both the recent manifestation and in general) https://www.youtube.com/watch?v=4rFMdKcR824

New comment by mockerell in "It is time to 'Correct the Map'"

mockerell — Fri, 15 Aug 2025 12:50:33 +0000

How does it fit into this xkcd?

https://xkcd.com/977/

New comment by mockerell in "The Fastest Way yet to Color Graphs"

mockerell — Fri, 16 May 2025 12:24:24 +0000

I think the comment referred to the phrase „a graph needs X (colors or whatever)“. For me, this can be read two ways: 1. „a graph always needs at least X colors“ or 2. „a graph always needs at most X colors“.

Personally, I would interpret this as option 1 (and so did the comment above I assume). In that case, the statement is wrong. But I’d prefer to specify „at most/ at least“ anyways.

Or even better, use actual vocabulary. „For every graph there exists a coloring with X colors.“ or „any graph can be coloured using X colors“.

PS: I also agree with the sentiment about quanta magazine. It’s hard to get some actual information from their articles if you know the topic.