3 ms·

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

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/Algorithms%20-%20Sanjoy%20Dasgupta%2C%20Christos%20H.%20Papadimitriou%2C%20and%20Umesh%20V.%20Vazirani.pdf https://github.com/eherbold/berkeleytextbooks/blob/master/Al...

moralestapia 2y 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 https://news.ycombinator.com/item?id=43179918
- iamnotempacc 2y 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.
  - moralestapia 2y 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?
- Ar-Curunir 2y 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)

moralestapia 2y 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 https://news.ycombinator.com/item?id=43179918

iamnotempacc 2y 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.
- moralestapia 2y 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?
Ar-Curunir 2y 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)