Ask HN: Solving problems by mapping to other problems that we know how to solve

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?"

Category Theory aims to do something like that

Complexity theory is traditionally into this approach. Prove a problem is NP hard by proving its an instance of another problem known to be NP hard.

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)

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

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

https://arxiv.org/abs/2009.02133

I thought repeatable techniques. Look into modeling and analytics.

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

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.

You can't solve NP-complete problems efficiently, but SAT (and 3SAT) is basically the best attempt at that complexity class.

-----------

The constraint satisfaction problem is another one that is sometimes used.

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.

---------

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).

---------

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.

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.)

> 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

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.

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).

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

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.

[1] https://ieeexplore.ieee.org/iel5/32/5010265/05010283.pdf

I studied machine learning and AI, I think it would be relevant for you to look at Transfer Learning - https://en.wikipedia.org/wiki/Transfer_learning

(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 https://medium.com/pandorabots-blog/aiml-tutorial-the-srai-t... ... 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 https://en.wikipedia.org/wiki/The_Master_Algorithm and his thinking behind Markov logic networks ... YMMV

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.

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.

It is also possible to prove that if an integer is divisible by 2, it is even. That's a different proof.

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.

All problems reducing to other problems in the technical sense are built on such foundations.

The specific area you're thinking of is theoretical computer science.

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.)

Here is an interesting practical way to turn Sparse linear regression solvers into Sparse PCA that’s not quite like reduction: https://arxiv.org/abs/1811.10106

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.

That's basically what SAT/SMT solvers do.

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.

This is an accessible paper on the general concepts:

https://arxiv.org/pdf/2101.11115.pdf

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”

John Baez has some inspiring work in this area as well.

Network Models is a good paper particularly on Network Operads

https://arxiv.org/abs/1711.00037

A pointer into what you are looking for may be duality:

https://en.m.wikipedia.org/wiki/Duality_(mathematics)

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.

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

TRIZ (https://en.m.wikipedia.org/wiki/TRIZ) 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.

In general, that kind of mapping is done all the time.

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).

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.

There's quite a bit of mathematics that's only 'true' relative to the assumption of the Riemann hypothesis. See eg https://mathoverflow.net/questions/17209/consequences-of-the...

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.

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)

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.

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.

I don't know if there is any specific field that covers this topic but rather I think every field _is_ this topic.

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.

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.

https://en.m.wikipedia.org/wiki/Category_theory

https://open.spotify.com/episode/6v01kNIPZZTmQk483nFy3H?si=8...

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.

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!

Research study observing the effectiveness of this ability in humans (pdf):

https://deepblue.lib.umich.edu/bitstream/handle/2027.42/2533...

Book on the wider subject:

https://www.amazon.com/Way-We-Think-Conceptual-Complexities/...