Is there a line of research that looks into solving difficult / intractable problems by finding a mapping that expresses them as different problems that we know how to solve?<p>A fairly surreal and probably overly optimistic example would be, for example, to solve traveling salesman problems using chess engines. What we would need is to find right mappings:
(1) from a traveling salesman problem to a chess position and,
(2) from a traveling salesman route to a chess move (or move sequence)<p>A general solution for a "compiler" that can translate between any pair of problems feels unrealistic but I can imagine developing a mapping between, say, a tic tac toe game and simple chess positions where you could:
(1) translate a tic tac toe position into a chess position
(2) solve the chess position
(3) translate the solution into a tic tac toe sequence<p>Any thoughts or pointers to relevant research would be much appreciated!
That’s called Mathematics. For example, most NP-complete problems we know of were proven to be NP-complete by showing them to be no easier than some other problems we know to be NP-complete. <a href="https://en.wikipedia.org/wiki/NP-completeness#NP-complete_problems" rel="nofollow">https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr...</a>:<p><i>“The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it”</i><p>As a second example, in combinatorial game theory, the Sprague–Grundy theorem states<p><i>“every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization”</i><p>(<a href="https://en.wikipedia.org/wiki/Sprague–Grundy_theorem" rel="nofollow">https://en.wikipedia.org/wiki/Sprague–Grundy_theorem</a>)<p>That means that, presented with an impartial game (both players can make the same moves, so chess is ruled out because white can’t move black pieces and vice versa) under the normal play convention (last player who can make a move wins), mathematicians look for a way to translate game positions to nimbers (<a href="https://en.wikipedia.org/wiki/Nimber" rel="nofollow">https://en.wikipedia.org/wiki/Nimber</a>) in order to learn how to play them.<p>Doing such mappings, if not trivial, requires creativity, so I think research on the subject would be in the psychology department.<p>Polya, in “How to Solve it” has some discussion on this (<a href="https://en.wikipedia.org/wiki/How_to_Solve_It#Heuristics" rel="nofollow">https://en.wikipedia.org/wiki/How_to_Solve_It#Heuristics</a>)
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":<p><a href="https://en.wikipedia.org/wiki/Reduction_(complexity)" rel="nofollow">https://en.wikipedia.org/wiki/Reduction_(complexity)</a><p>In practice, there are many cases where people use SAT solvers for other problems.
For some examples:<p><a href="http://homepages.math.uic.edu/~jan/mcs401/reductions.pdf" rel="nofollow">http://homepages.math.uic.edu/~jan/mcs401/reductions.pdf</a>
Your question immediately made me think of G. Polya's classic book (and research) from 1945 "How to solve it", which devotes a large part to the question "Here is a problem related to yours and solved before. Could you use it?"<p>A small excerpt: "… We have to look around for closely related problems; we look at the unknown, or we look for a formerly solved problem which is linked to our present one by Generalization, Specialization, or Analogy"
This is the general concept of math: to prove one set contains another set. In some cases you prove set equality by showing each side contains the other.<p>A simple example of this is: all even integers are divisible by two. That's two sets: the set of even numbers and the set of numbers divisible by two. For any x that is an even number, it is equal to 2k for some integer k. This implies that x/2 = 2k/2 = k. Since x/2 is an integer, it is divisible by 2 QED.<p>It is also possible to prove that if an integer is divisible by 2, it is even. That's a different proof.<p>The fact that you can solve problem A in terms of problem B doesn't always mean you can solve problem B in terms of problem A. Just because great minds think alike, doesn't mean people who think alike are great minds.<p>All problems reducing to other problems in the technical sense are built on such foundations.<p>The specific area you're thinking of is theoretical computer science.<p>You might like the textbook "Introduction to the theory of computation" by sipser. It starts by showing the mutual-problem-reducibility of regular languages (AKA the language of deteinistic finite automata / regular expressions) and moves step by step into Turing machines which support general purpose programming languages. And beyond (languages which can only be conputed by hypothetical machines which we don't know how to build in reality.)
This is commonly called a reduction in complexity theory, and is used often in hardness proofs. Here is a class from an incredible teacher, Erik Demaine , about such problems which may be helpful:<p>MIT 6.890 <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/" rel="nofollow">https://ocw.mit.edu/courses/electrical-engineering-and-compu...</a><p>Basic idea is map a hard problem A (e.g TSP) to some other problem X (e.g chess) by finding “gadgets” then you know X is at-least as hard as A (a lower bound on X).
The satisfaction problem is considered the "ultimate" problem to reduce into. Because SAT is very flexible in representation, is NP complete (and therefore a huge variety of problems map to it), and sometimes is efficient.<p>You can't solve NP-complete problems efficiently, but SAT (and 3SAT) is basically the best attempt at that complexity class.<p>-----------<p>The constraint satisfaction problem is another one that is sometimes used.<p>For example, Sudoku, Traveling Salesman, coloring problems and more all reduce into the 3SAT problem. However, a dedicated traveling-salesman solver will be faster than pretty much any general purpose 3SAT solver, but its still easier to use another person's solver than writing your own.<p>---------<p>An intriguing "simpler" problem is the maximum-flow problem, which is surprisingly flexible and usable in many many algorithms. Its not as widely applicable as 3SAT is, but maximum-flow is "efficient" to solve (in P-time and P-space).<p>---------<p>A good book into this (including these "cannonical" problems, like maximum flow or 3SAT) is "Algorithm Design" by Jon Kleinberg and Eva Tardos. This only covers the basics of course. 3SAT and constraint satisfaction are their own respective fields with basically their own branches of mathematics.<p>A lot of Graph algorithms are also worth knowing. It seems like many, many problems map into graph algorithms (max-clique, topological sort, minimum spanning tree, etc. etc.)<p>> A general solution for a "compiler" that can translate between any pair of problems feels unrealistic but I can imagine developing a mapping between, say, a tic tac toe game and simple chess positions where you could: (1) translate a tic tac toe position into a chess position (2) solve the chess position (3) translate the solution into a tic tac toe sequence<p>Yup, that's a 3SAT solver for ya. It will solve the problem, eventually, but 3SAT is NP complete, so the heat-death of the universe may come about before the answer comes out.<p>If you know your problem is less complex than NP-complete, you'll want to map it to some other problem that's got less complexity (so that the algorithm finishes faster).
So the answer I have isn't exactly what you're looking for, which I think is an algorithmic/machine learning architecture that can transfer concepts found in problems.<p>Just wanted to share for anyone interested that there is in depth research and theory developed in cognitive science concerning the way people use what the field calls conceptual blending to make sense of unfamiliar subjects with familiar concepts. Maybe it's worth taking inspiration from!<p>Research study observing the effectiveness of this ability in humans (pdf):<p><a href="https://deepblue.lib.umich.edu/bitstream/handle/2027.42/25331/0000776.pdf?sequence=1" rel="nofollow">https://deepblue.lib.umich.edu/bitstream/handle/2027.42/2533...</a><p>Book on the wider subject:<p><a href="https://www.amazon.com/Way-We-Think-Conceptual-Complexities/dp/0465087868" rel="nofollow">https://www.amazon.com/Way-We-Think-Conceptual-Complexities/...</a>
From what I’ve understood of category theory that sounds like exactly what you are looking for. I would recommend listening to the latest 3b1b podcast where Grant interviews Tai-danae Bradley who studies category theory, really fascinating.<p><a href="https://en.m.wikipedia.org/wiki/Category_theory" rel="nofollow">https://en.m.wikipedia.org/wiki/Category_theory</a><p><a href="https://open.spotify.com/episode/6v01kNIPZZTmQk483nFy3H?si=86tjYVziQNSM9I9v-izK8w" rel="nofollow">https://open.spotify.com/episode/6v01kNIPZZTmQk483nFy3H?si=8...</a>
I'd say that this is in fact most of what mathematics is. Seriously! In Linear Algebra we learn about things like Matrix Decompositions (QR, LU, Cholesky, Rank, etc). In calculus we learn about change of variables and Jacobians that allow us to convert from one space to another. We also use change of variables frequently in statistics and metric theory (in ML we have Normalizing Flows). In proofs we often abstract to the opposite of a problem and prove that the opposite doesn't work. We do this because we can't prove the thing we want directly. In optimization we have dual problems where we convert a problem to an easier one. We do this frequently in algorithms and most motivating examples for dynamic programming are doing exactly this. Topology is the study of looking at a mug and doughnut and calling them the same thing. Similarly in knot theory. I could seriously go on and on.<p>All over mathematics and problem solving we frequently find many techniques of converting the problem we are trying to solve into something easier. I'd even argue that this is what mathematics and most of science is in general. After all, everything we are doing is an approximation. We can't solve the universe, but we can dictate what we see with a carefully laid out language (physics) and use that to describe what we see and make predictions based on it. Everything is just a model and a model is a map. (I'd go as far as arguing that we do this with language, not just in analogies, but in so far as saying that the existence of language itself is a map from a difficult and intractable problem to an easier one)<p>The thing though is that not everything can be mapped to anything else. That's the real hard part. For example you would not have a bijective mapping from tic-tac-toe to chess and you can prove this by looking at the number of game states that each contains. TTT to chess would clearly be a non-injective mapping.<p>So it is hard to give you a tip into specific forms of research without knowing more specificity. I would encourage you to see the world like this. This is why many of these fields will encourage you to look at problems through different lenses. Why you'll often see many of the big breakthroughs in fields are connecting ideas from other fields (Nash and Einstein are notable and relatively recent examples). There was Terrence Tao's post about how to solve problems on HN just the other day (and many references to Polya's book) and I'll say that you will find the same recommendations there.<p>I don't know if there is any specific field that covers this topic but rather I think every field _is_ this topic.
Soloway's work [1] might speak to you. In essence, Soloway referred to this association as "templates", in which we associate problems with those we've seen in the past. While the linked study points at it as a potential negative, you aren't far off in assuming its beneficial as well. When I teach Data Structures and AI courses, I refer it the phenomena as "neutralizing the problem" (borrowed for my years training martial arts). Again, the idea is to model the problem as something we've something seen before - because then, we have solutions for it! The biggest issue is knowing how to best model the problems so that we're not trying to shoehorn everything into a particularly inefficient solution. However, this is a "fun" bit of research, seeing which models best work with which problems.<p>[1] <a href="https://ieeexplore.ieee.org/iel5/32/5010265/05010283.pdf" rel="nofollow">https://ieeexplore.ieee.org/iel5/32/5010265/05010283.pdf</a>
This is very fundamental not only in maths but in theoretical computer science in general.
Even to prove how "hard" a problem is. E.g. look into (Turing/many-one) reductions [1]<p>Many problems can be reduced to SAT and then you can employ an off-the-shelf SAT/SMT solver to solve it for you. Etc etc.<p>But in general, being able to reduce problem A to problem B implies that A is not harder than B. I.e., to show that a problem P is undecidable, you can reduce the Halting problem to P.<p>TSP is NP-hard and can be reduced to SAT, then solved with a SAT solver.
But something like determining whether a player has a winning strategy in unrestricted chess (with an nxn board, for arbitrary n) is in EXPTIME and can't be reduced to an "easier" problem.<p>Edit: Someone ITT also mentioned ILP (integer linear programming). Also a good example. E.g., many optimization programs can be mapped to ILP.<p>[1] <a href="https://en.wikipedia.org/wiki/Turing_reduction" rel="nofollow">https://en.wikipedia.org/wiki/Turing_reduction</a>
TRIZ (<a href="https://en.m.wikipedia.org/wiki/TRIZ" rel="nofollow">https://en.m.wikipedia.org/wiki/TRIZ</a>) is a methodology that tries to solve problems by mapping them to a set of 40 "generic problems". It's not focused on algorithms per se, but on industrial problems.
A pointer into what you are looking for may be duality:<p><a href="https://en.m.wikipedia.org/wiki/Duality_(mathematics)" rel="nofollow">https://en.m.wikipedia.org/wiki/Duality_(mathematics)</a><p>For example, in geometry, there is an equivalence between Voronoi diagrams, Delanauy triangulation, convex hulls and plane intersections. This is of very practical importance (for me at least!) because you can reuse non trivial algorithm/libraries that solve one problem to solve the other. Duality is also very important in optimization, where you transform a problem, the primal, into it's dual and solve one or both of them simultaneously.<p>I have not found a lot of info in "pure" duality, it's a meta-concept present in a lot of different mathematical areas but I'm sure there must be mathematicians looking at it
There is Frame Innovation by Kees Dorst. It takes at look at complex problems NOT by slicing them up and trying to solve each ‘slice’ but rather tries to look at the entire situation as a whole and -with your team- formulate a better and more desired situation. It uses ‘frames’ from other disciplines and tries to achieve a multidisciplinary view where each field combines knowledge. The idea is not always to solve the problem because really co
Pled problems can’t just be solved. Rather it looks to work towards a better situation. It also relies on Systems Thinking to study what system revolves around a problem and where one can intervene.
Everyone already mentioned mathematics but I'd also like to mention Operations Research as a field that's basically all about translating complex business problems into mathematical models that can be efficiently solved.<p>In practice this almost always means translating to the formats used by (Mixed) Integer Programming (MIP) solvers, Constraint Programming (CP) solvers or SAT solvers.<p>Satisfiability Modulo Theories (SMT) solvers are used more in the formal verification realm, but they can also be used for the same purpose, the problems solved by these tools are all NP-complete so you can with more or less effort translate any NP problem to them.
Well, it's from the field of mathematics, but you might be interested in the book "How to Solve it" by Polya. One of Polya's methods is to ask "Do I know how to solve a related problem?"
I recently read the book: "The Algorithm Design Manual" by Skiena. Chapter 11 is a good resource for this line of inquiry concerning reductions/translations between problems and NP-Completeness.
From “The Origin of Consciousness in the Breakdown of the Bicameral Mind”:<p>“Understanding a thing is to arrive at a metaphor for that thing by substituting something more familiar to us. And the feeling of familiarity is the feeling of understanding.”<p>“Understanding in science is the feeling of similarity between complicated data and a familiar model.”<p>“The Bohr model of the atom is that of a proton surrounded by orbiting electrons. It is something like the pattern of the solar system, and that is indeed one of its metaphoric sources.”
I’ve wondered the same thing as i run into environmental management problems that seem to fit this model. Work being done with Network Operads, and process calculus is applicable to this line of thought.<p>This is an accessible paper on the general concepts:<p><a href="https://arxiv.org/pdf/2101.11115.pdf" rel="nofollow">https://arxiv.org/pdf/2101.11115.pdf</a><p>Abstract:
“We solve complex problems by separating them into manageable parts [2,86]. Human designers do this intuitively, but details can quickly overwhelm intuition. Multiple aspects of a problem may lead to distinct decompositions and complementary models of a system– e.g. competing considerations for cyberphysical systems [63,87]–or simulation of behavior at many levels of fidelity–e.g. in modeling and simulation [88]–leading to a spectrum of models which are challenging to align. We argue that operads, formal tools developed to compose geometric and algebraic objects, are uniquely suited to separate complex systems into manageable parts and maintain alignment across complementary models”<p>John Baez has some inspiring work in this area as well.<p>Network Models is a good paper particularly on Network Operads<p><a href="https://arxiv.org/abs/1711.00037" rel="nofollow">https://arxiv.org/abs/1711.00037</a>
I studied machine learning and AI, I think it would be relevant for you to look at Transfer Learning - <a href="https://en.wikipedia.org/wiki/Transfer_learning" rel="nofollow">https://en.wikipedia.org/wiki/Transfer_learning</a><p>(By the way if anyone is looking for a Software Engineering Manager in New York City with a specialization in AI, see my profile and get in touch!)
This was done (somewhat) a while back with linguistics in the form of symbolic reduction, while it has no direct interpretation to code it could be used that way (or at least I saw it that way), either way I found it to be one of the more interesting ideas in AIML at the time when we were developing the spec, but I don't take credit for it. It is somewhat explained at <a href="https://medium.com/pandorabots-blog/aiml-tutorial-the-srai-tag-5bb1f9d08169" rel="nofollow">https://medium.com/pandorabots-blog/aiml-tutorial-the-srai-t...</a> ... all these tags are just wrappers around an execution graph but it was a neat way to filter your way down to a static answer. I tend to think about it when I read <a href="https://en.wikipedia.org/wiki/The_Master_Algorithm" rel="nofollow">https://en.wikipedia.org/wiki/The_Master_Algorithm</a> and his thinking behind Markov logic networks ... YMMV
It depends. I think most real world problems are complex and usually do not have comprehensively defined rules. I think it's extremely unlikely that a complex issue will share all the attributes of another complex problem. I say this assuming we are looking at the n-order impacts of a system or solution.<p>It's possible that we could decompose the complex problems into simpler ones and the solution for a subset could be shared. Although in most cases I feel that the effects will be at least slightly different as far as the n-order effects.<p>For example, the solution to inflation could be tying a number to automatically adjust based on CPI. This might make sense for a SS payment and COLA. It might not make sense for basis adjustment of school property taxes as other variables could adjust the revenue need, like decrease in students or increase in funding from other sources. It looks like they map on the surface, but not when you dig deeper.
You might be interested in the concept of "duality" often used in e.g. theoretical physics: <a href="https://en.wikipedia.org/wiki/Duality_(mathematics)" rel="nofollow">https://en.wikipedia.org/wiki/Duality_(mathematics)</a><p>If you want to be even more general, check out a field of mathematics called category theory (<a href="https://en.wikipedia.org/wiki/Category_theory" rel="nofollow">https://en.wikipedia.org/wiki/Category_theory</a>). Its' central idea is to describe mathematical structures in terms of "objects" and their relationship with each other (called morphisms). I'm not extremely knowledgeful in this subject, but I believe mostly everything you get out of categorical theoretical treatment is too generic to be useful, but has resulted in some real results in e.g. algebraic geometry.
This discussion reminds me of "Analogical modeling" that was taught to us in a course titled "Mechatronics". They taught us how to model physical systems / phenomenon using electrical circuits.
This was especially useful in analyzing systems that had a mix of mechanical components (springs, tanks, pistons, levers) and electronics (resistor, capacitor, amplifiers). You would draw a big circuit diagram that non only included actual electrical components but also electrical analogues of the mechanical components. This way you will end up with just an electrical circuit and use only the laws related to electric networks (Kirchoff, Thevenin) to analyze the behavior of the system.<p><a href="https://en.wikipedia.org/wiki/Analogical_models" rel="nofollow">https://en.wikipedia.org/wiki/Analogical_models</a>
My favourite example of this is how no limit Texas holdem was solved.<p>This game is of course an imperfect information game (you don’t know your opponents hole cards). We have lots of great algos for perfect information games but not imperfect.<p>So what the researches did is they mapped hold em to a perfect information game by tweaking it: now nobody knows their hole cards and all players must publicly announce their strategy to a “referee”. Then the referee looks at the players cards and places bets on behalf of the players. A player’s strategy looks something like: if I have a pair of aces then I want to raise 94% of the time and call 6% of the time and fold 0% of the time etc etc.<p>You know your opponent’s strategy too (as they have announced it like you did to the referee) so you can now iterate and optimise your strategies which will approach a Nash equilibrium.
Translating a solution from one problem domain to another is called "transfer" in cognitive science. There's some theoretical and empirical work done on the topic of transfer (e.g. <a href="https://www.tandfonline.com/doi/full/10.1080/13546780802490186" rel="nofollow">https://www.tandfonline.com/doi/full/10.1080/135467808024901...</a>) but as far as I'm aware, there is not a mature "general theory of transfer" that can be computationally implemented. That's still in the fictional "Glass Bead Game" territory. However, you may want to take a look at that literature for broader picture theory on the issue. It's closely related to the fairly vast literature on insight problem solving, which you might be interested in.
In general, that kind of mapping is done all the time.<p>As an example from mathematics Fermat's Last Theorem was first proven conditionally on a few conjectures. In your words, it was mapped to these conjectures (though not bijectively, Fermat's theorem didn't imply these conjectures as far as I know).<p>Later on Andrew Wiles proved the last of these conjectures, thus establishing Fermat's Last Theorem as absolutely true and not just relative to these conjectures.<p>There's quite a bit of mathematics that's only 'true' relative to the assumption of the Riemann hypothesis. See eg <a href="https://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis" rel="nofollow">https://mathoverflow.net/questions/17209/consequences-of-the...</a>
Charlie Munger's mental models are particularly famous for applying this technique to make intelligent decisions in life. Many of them are documented here:
<a href="https://fs.blog/mental-models/" rel="nofollow">https://fs.blog/mental-models/</a><p>Another one from System Designers is called an Archetype. Most problems can be reduced to an archetype for understanding and solving effectively.
<a href="https://thesystemsthinker.com/topics/archetypes/" rel="nofollow">https://thesystemsthinker.com/topics/archetypes/</a>
I have no advice, but this is a very powerful way of looking for solutions. Today I ran into some physics postdocs at the skatepark. They told me about their research doing fluid mech experiments to simulate the behaviour of space near but not in a black hole. One of them (Sam) wrote his highly entertaining PhD thesis about the analogy of a draining bathtub's vortex with black holes<p><a href="https://arxiv.org/abs/2009.02133" rel="nofollow">https://arxiv.org/abs/2009.02133</a>
I own a book that may be relevant: "Bypasses: A Simple Approach to Complexity" by Z. A. Melzak, (New York, Wiley, 1983) 0-471-86854-X, or maybe it's too theoretical.<p>A borrowable digital copy is at the Internet Archive: <a href="https://archive.org/details/bypasses00zdzi" rel="nofollow">https://archive.org/details/bypasses00zdzi</a>
This is an even more interesting question on a broader definition - OP and a lot of the answers refer to math, which is understandable given most of our backgrounds, but I've always wondered what about complex, inter-domain problem solving?<p>How do we map programming to understanding genetic codes?<p>How do we map psychological research or zoological data to operations research?
Here is an interesting practical way to turn Sparse linear regression solvers into Sparse PCA that’s not quite like reduction: <a href="https://arxiv.org/abs/1811.10106" rel="nofollow">https://arxiv.org/abs/1811.10106</a>
I studied physics in undergrad. This was basically my impression: most problems are really hard but we don’t need to solve all of the cases. Just hammer on it until it looks like a harmonic oscillator and then apply the known solution.
Godel numbering does this for Logic. Reading GEB rn so top of mind.<p><a href="https://en.wikipedia.org/wiki/G%C3%B6del_numbering" rel="nofollow">https://en.wikipedia.org/wiki/G%C3%B6del_numbering</a>
If you watch any 3Blue1Brown, Standup Math and/or Veritasium, as many noted, you will notice that this is often how it works in Math.<p>They often start from something unrelated and work towards solving something very different.
But in order for a valid mapping to exist it needs to fit into what's mapping. Following your example, how do you map chess to the salesman problem if chess is not optimizing the same thing?
A number of approximations use the information on the inputs to simplify the equation. Such as sin(x)/x near zero, is about 1. So looking for opportunities like that can help
What you're describing is the central concept in Computational Complexity Theory. It's how complexity classes like P, NP, #P, etc. are defined.
I think the game Nim is a great example of this! All non partisan Combinatorial games reduce to Nim. So you just solve this one game and you solve all xoxo