undefined | Better HN

0 pointsriwsky1y ago0 comments

Wikipedia: “Intuitively, problem A is reducible to problem B, if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently.”

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.

0 comments

moralestapia1y ago

Hmm, the discussion here requires a deeper understanding of these concepts, much deeper than a casual read of one sentence picked from Wikipedia.

I wouldn't have wrote that sentence to introduce people to reduction, because it misses a very important property of the operation that changes the whole thing. That sentence could lead you to think that reducing A <= B is the same as reducing B <= A, which is not always true. To see why, try to understand [1].

There's a reason why the reduction equivalence classes form a preorder, as stated on the Wikipedia page you quoted.

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

riwskyOP1y ago

> When this is true, solving A cannot be harder than solving B. "Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, expensive need for extra hardware processor cores for a parallel solution compared to a single-threaded solution, etc.). The existence of a reduction from A to B can be written in the shorthand notation A ≤m B, usually with a subscript on the ≤ to indicate the type of reduction being used (m : mapping reduction, p : polynomial reduction).

The article indeed argues that solving n-day vulnerability discovery is no harder than document ranking. It does not argue that document ranking is no harder than n-day discovery, because it assumes that most people already would assume that; nor does it set out to disprove it.

moralestapia1y ago

To be honest, even the article is not a formal attempt at proving all of this, nor does it have to, it's a bit of a conjecture, but anyway.

My reasoning goes along this line, which of the following two sentences you think is more likely to be true?

A. All n-day vulnerability discovery problems can be mapped to a document rerank problem.

B. Some n-day vulnerability discovery problems can be mapped to a document rerank problem.

I lean towards B, without any proof for it. Hence why I think the correct way is to reduce reranks into n-days (and all the other "hard problems").

If you think A is true, you still have to show that all reranks can be reduced to n-days, to be rigorous and able to say that your proposed algorithm works in both domains.

In the end it could be that both alternatives are equivalent, but it's easier to just say "reranks can be reduced to n-days" and because of this "some n-days can be adequately solved by my algorithm that works in reranks".

1 more reply

j / k navigate · click thread line to collapse

0 comments

moralestapia1y ago

Hmm, the discussion here requires a deeper understanding of these concepts, much deeper than a casual read of one sentence picked from Wikipedia.

There's a reason why the reduction equivalence classes form a preorder, as stated on the Wikipedia page you quoted.

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

riwskyOP1y ago

moralestapia1y ago

To be honest, even the article is not a formal attempt at proving all of this, nor does it have to, it's a bit of a conjecture, but anyway.

My reasoning goes along this line, which of the following two sentences you think is more likely to be true?

A. All n-day vulnerability discovery problems can be mapped to a document rerank problem.

B. Some n-day vulnerability discovery problems can be mapped to a document rerank problem.

I lean towards B, without any proof for it. Hence why I think the correct way is to reduce reranks into n-days (and all the other "hard problems").

If you think A is true, you still have to show that all reranks can be reduced to n-days, to be rigorous and able to say that your proposed algorithm works in both domains.

1 more reply

j / k navigate · click thread line to collapse