Hacker News new | ask | show | jobs
by Ar-Curunir 478 days ago
If A reduces to B, it means that an algorithm implementing B can be used (with some pre- and post-processing) to solve A.

If A reduces to B, it means that B is at least as hard as A.

This is the standard terminology in every theoretical computer science; see for example the DPV textbook on page 210: https://github.com/eherbold/berkeleytextbooks/blob/master/Al...
1 comments
moralestapia 478 days ago
Isn't that what I wrote on [1]?

Do you have something to add or is it just ... a confirmation?

Weird.

1: https://news.ycombinator.com/item?id=43179918

link
iamnotempacc 478 days ago
Are you trolling or what. Let's see what's written in the comment above.

> If A reduces to B, it means that an algorithm implementing B can be used (with some pre- and post-processing) to solve A.

Here we say that that we can solve a "hard problem" if we can express it in terms of the "Document Ranking" problem.

Let's rewrite that quoted sentence:

An algorithm implementing "Document Ranking" can be used (with some pre- and post-processing) to solve "Hard problem".

Let's do substitution in the first part of the sentence, "If A reduces to B", where A is "hard problem" and B is "Document Ranking":

Hard problem reduces to Document Ranking.

That means EXACTLY that we can USE Document Ranking to SOLVE the Hard Problem. Just as we wanted.

link
moralestapia 478 days ago
Ar-Curunir: If A reduces to B, it means that an algorithm implementing B can be used (with some pre- and post-processing) to solve A.

moralestapia: If I transform B to A and I know the solution to A, then I solved B.

Ar-Curunir: If A reduces to B, it means that B is at least as hard as A.

moralestapia: [...] B is at least as complex as A

Can you even read?

link
Ar-Curunir 478 days ago
No, that is not what you wrote. You wrote “document ranking reduces to these hard problems", which means that document ranking can be solved with an algorithm for one of those hard problems. The article discusses the opposite: those hard problems can be solved by using algorithms for document ranking (which is itself a non-trivial problem)
link