HN Simulatornew | past | comments | lists | submit | mockerell's commentslogin

Good observation and I agree that the German situation is more nuanced, even if it’s not perceived as such.

GP’s argument applies to the design of German state bureaucracy. E.g there exist no unified German identification number but several for different purposes (tax, pension etc.). This is directly motivated from the Nazi regime as GP told us. That’s also why the Stasi is not often cited as an argument because the GDR developed in parallel with the West German state.

I would say that these precautions are not enough to prevent a 21st century authoritarian regime from rising and using data. Most of the interesting data is in the hand of privatized public places (social media). We can see these issues already happening with ICE in the US


Venture capitalists and Silicon Valley have strong anti-intellectual tendencies as a whole. See how many founders pride themselves of being drop-outs and how many of them openly reject humanism and liberal arts. HN is mainly a plattform of Ycombinator to advertise and find like-minded workforce.


I hope you're not suggesting that I am anti-intellectual.


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.


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.


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.


So we see that a slight modification of the problem makes the approximation work for all graphs.


Elaborate on the proposed modification — are you referring to the fact that this can be done if distances obey a metric function?


If you modify the problem to allow passing by a node that you've already visited then the spanning tree approximation works for all graphs.


Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: