Say you have a problem that you know reasonably well (A-type) and another one that you're studying (B-type), intuitively, you'd say "If I transform B to A and I know the solution to A, then I solved B" but what you actually need to do is to transform A to B, this is called "reducing A to B", for some reason, and then you can say things like "B is at least as complex as A" and "I can solve some instances of B the way I solve the general case of A".
This doesn't really apply here since neither the "hard problems" TFA mentions nor "document ranking" are canonical problems that you would typically use in these proofs, but since he's borrowing the term from this part of CS I wanted to make that remark on its proper use. Hence why I wrote "minor nitpick".
The reduce operation that you mentioned doesn't make sense within the context of the article.
The article takes for granted that LLM-driven listwise comparisons efficiently solve document ranking (problem B), and then shows this can also be used as a subroutine to solve various hard problems like vulnerability analysis (problems A) efficiently.
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...
Do you have something to add or is it just ... a confirmation?
Weird.
> 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.
