4 ms·

This isn't a complete answer to your question, because it's generally more theoretical than operational, but the thing you're describing is often called "reduct

This isn't a complete answer to your question, because it's generally more theoretical than operational, but the thing you're describing is often called "reduction": https://en.wikipedia.org/wiki/Reduction_(complexity) https://en.wikipedia.org/wiki/Reduction_(complexity) In practice, there are many cases where people use SAT solvers for other problems. For some examples: http://homepages.math.uic.edu/~jan/mcs401/reductions.pdf http://homepages.math.uic.edu/~jan/mcs401/reductions.pdf

mathcass 5y ago
I came here to upvote this and add on some more resources. (I read the main comment and literally thought "reductions.") John Langford of Microsoft Research (and formerly of Yahoo! Research) has some some extensive theoretical and practical work here. In particular as they apply to machine learning problems. Check out his page on this[1]. I'd also recommend checking out Vowpal Wabbit[2] which is essentially a working implementation of many of these reductions in ML. 1. https://hunch.net/~jl/projects/reductions/reductions.html https://hunch.net/~jl/projects/reductions/reductions.html 2. https://vowpalwabbit.org/ https://vowpalwabbit.org/
pyrale 5y ago
To complete the answer, the field of research interested in solving this kind of problem is called operational research.
a-dub 5y ago
most cs programs have an undergraduate course called "cs theory" or "computability" which is usually some introduction to some theory behind language definition and language parsing followed by abstract models for computation (turing machines) and finally explorations of what's "computable." (google for "computability theory automata books" for a bunch of different texts) the last one (what's computable) forms the basis for a lot of (all?) cryptography and is filled with all sorts of really fun and not at all hard to master proofs that are just reductions at their core.
- a-dub 5y ago
  but sort of getting more at your core point, borrowing across fields is basically a technique for problem solving. in domains like, applied math, what you tend to find is that everyone in different fields are often doing the same thing but have different names for it. statisticians, electrical engineers, data scientists and physicists will all often use the same math (linear systems) but with very different names attached.

mathcass 5y ago

I came here to upvote this and add on some more resources. (I read the main comment and literally thought "reductions.") John Langford of Microsoft Research (and formerly of Yahoo! Research) has some some extensive theoretical and practical work here. In particular as they apply to machine learning problems. Check out his page on this[1]. I'd also recommend checking out Vowpal Wabbit[2] which is essentially a working implementation of many of these reductions in ML. 1. https://hunch.net/~jl/projects/reductions/reductions.html https://hunch.net/~jl/projects/reductions/reductions.html 2. https://vowpalwabbit.org/ https://vowpalwabbit.org/

pyrale 5y ago

To complete the answer, the field of research interested in solving this kind of problem is called operational research.

a-dub 5y ago

most cs programs have an undergraduate course called "cs theory" or "computability" which is usually some introduction to some theory behind language definition and language parsing followed by abstract models for computation (turing machines) and finally explorations of what's "computable." (google for "computability theory automata books" for a bunch of different texts) the last one (what's computable) forms the basis for a lot of (all?) cryptography and is filled with all sorts of really fun and not at all hard to master proofs that are just reductions at their core.

a-dub 5y ago
but sort of getting more at your core point, borrowing across fields is basically a technique for problem solving. in domains like, applied math, what you tend to find is that everyone in different fields are often doing the same thing but have different names for it. statisticians, electrical engineers, data scientists and physicists will all often use the same math (linear systems) but with very different names attached.