3 ms·

> 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 conte

by riwsky 2y 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.

moralestapia 2y 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. or 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".
- riwsky 2y ago
  Even if you believe B, that’s still not reducing document ranking to n-day vulnerability discovery; it’s “reducing some n-day discovery to document ranking”. A does not require demonstrating doc-rank problems map to n-day problems, since reduction isn’t required to be symmetric. Where you might be getting caught up is in the mapping of problems vs the mapping of solutions. “Nday reduces to docrank” implies we can turn every nday problem into a docrank problem, and every docrank solution into an nday solution, but does not say anything about whether we can turn docrank problems into nday problems, or nday solutions into docrank solutions.
  - moralestapia 2y ago
    >Even if you believe B, that’s still not reducing [...] I agree. >A does not require demonstrating doc-rank problems map to n-day problems Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. >since reduction isn’t required to be symmetric That's exactly my point. A <= B is not necessarily the same as B <= A, even though in some cases, at a first glance, it seems to be the case. Your choice of which one is A or B will change how you construct whatever proof you want to come up with. I would choose to do "reduce rerank to n-day (and all others)", because it feels like it would be easier down the road, but also because one typically reduces the problem that one knows best (more general, known bounds solutions, etc...) into the one that you're studying. That's why I wrote "minor nitpick". Think about the textbook example of 3-SAT and all other problems it reduces to: clique, vertex cover, independent set, ... one does not reduce these problems into 3-SAT, it's the other way around. That doesn't mean you couldn't, some of them may have an complete equivalences to 3-SAT, but it's just easier to work out everything if you go from 3-SAT to the rest. My argument is the same, rerank is the thing that you reduce to all others.
    - riwsky 2y ago
      > >A does not require demonstrating doc-rank problems map to n-day problems > Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. But the article isn’t mapping docrank to nday, nor is it claiming to reduce docrank to nday. Its choice of A and B is clear. Nday didn’t have an understood solution to leverage like docrank did. > one typically reduces the problem that one knows best (more general, known bounds solutions, etc...) into the one that you're studying Wikipedia: “”” There are two main situations where we need to use reductions: First, we find ourselves trying to solve a problem that is similar to a problem we've already solved. In these cases, often a quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve these using our existing solution, and then use these to obtain our final solution. This is perhaps the most obvious use of reductions. “”” This is what the article does, reducing the new nday problem into the known docrank one. “”” Second: suppose we have a problem that we've proven is hard to solve, and we have a similar new problem. We might suspect that it is also hard to solve. We argue by contradiction: suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, we have a contradiction. This establishes that the new problem is also hard. “”” This is your ‘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’. “Nday discovery is at least as complicated as document ranking” is obvious, though, which is why it’s not the subject of a blog post.

by riwsky 2y ago

moralestapia 2y 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. or 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".

riwsky 2y ago
Even if you believe B, that’s still not reducing document ranking to n-day vulnerability discovery; it’s “reducing some n-day discovery to document ranking”. A does not require demonstrating doc-rank problems map to n-day problems, since reduction isn’t required to be symmetric. Where you might be getting caught up is in the mapping of problems vs the mapping of solutions. “Nday reduces to docrank” implies we can turn every nday problem into a docrank problem, and every docrank solution into an nday solution, but does not say anything about whether we can turn docrank problems into nday problems, or nday solutions into docrank solutions.
- moralestapia 2y ago
  >Even if you believe B, that’s still not reducing [...] I agree. >A does not require demonstrating doc-rank problems map to n-day problems Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. >since reduction isn’t required to be symmetric That's exactly my point. A <= B is not necessarily the same as B <= A, even though in some cases, at a first glance, it seems to be the case. Your choice of which one is A or B will change how you construct whatever proof you want to come up with. I would choose to do "reduce rerank to n-day (and all others)", because it feels like it would be easier down the road, but also because one typically reduces the problem that one knows best (more general, known bounds solutions, etc...) into the one that you're studying. That's why I wrote "minor nitpick". Think about the textbook example of 3-SAT and all other problems it reduces to: clique, vertex cover, independent set, ... one does not reduce these problems into 3-SAT, it's the other way around. That doesn't mean you couldn't, some of them may have an complete equivalences to 3-SAT, but it's just easier to work out everything if you go from 3-SAT to the rest. My argument is the same, rerank is the thing that you reduce to all others.
  - riwsky 2y ago
    > >A does not require demonstrating doc-rank problems map to n-day problems > Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. But the article isn’t mapping docrank to nday, nor is it claiming to reduce docrank to nday. Its choice of A and B is clear. Nday didn’t have an understood solution to leverage like docrank did. > one typically reduces the problem that one knows best (more general, known bounds solutions, etc...) into the one that you're studying Wikipedia: “”” There are two main situations where we need to use reductions: First, we find ourselves trying to solve a problem that is similar to a problem we've already solved. In these cases, often a quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve these using our existing solution, and then use these to obtain our final solution. This is perhaps the most obvious use of reductions. “”” This is what the article does, reducing the new nday problem into the known docrank one. “”” Second: suppose we have a problem that we've proven is hard to solve, and we have a similar new problem. We might suspect that it is also hard to solve. We argue by contradiction: suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, we have a contradiction. This establishes that the new problem is also hard. “”” This is your ‘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’. “Nday discovery is at least as complicated as document ranking” is obvious, though, which is why it’s not the subject of a blog post.