Ask HN: Solving problems by mapping to other problems that we know how to solve
80 comments
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. https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr...:
“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”
As a second example, in combinatorial game theory, the Sprague–Grundy theorem states
“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”
(https://en.wikipedia.org/wiki/Sprague–Grundy_theorem)
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 (https://en.wikipedia.org/wiki/Nimber) in order to learn how to play them.
Doing such mappings, if not trivial, requires creativity, so I think research on the subject would be in the psychology department.
Polya, in “How to Solve it” has some discussion on this (https://en.wikipedia.org/wiki/How_to_Solve_It#Heuristics)
“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”
As a second example, in combinatorial game theory, the Sprague–Grundy theorem states
“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”
(https://en.wikipedia.org/wiki/Sprague–Grundy_theorem)
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 (https://en.wikipedia.org/wiki/Nimber) in order to learn how to play them.
Doing such mappings, if not trivial, requires creativity, so I think research on the subject would be in the psychology department.
Polya, in “How to Solve it” has some discussion on this (https://en.wikipedia.org/wiki/How_to_Solve_It#Heuristics)
Good answer. Seems like a relevant time to post an old math joke:
There were two men trying to decide what to do for a living. They went to see a counselor, and he decided that they had good problem solving skills.
He tried a test to narrow the area of specialty. He put each man in a room with a stove, a bucket of water, and an empty pot on the stove. He said, “Boil some water in the pot.” Both men filled the pot with water from the bucket and turned on the burner to boil the water.
Next, he put them into a room with a stove, a bucket of water, and a pot full of water on the stove. Again, he said, “Boil the water in the pot.” The first man immediately turned on the burner. The counselor told him to be an Engineer. The second man emptied the pot and proudly said that now the problem is reduced to the previously solved problem. The counselor told him to be a mathematician.
This version from: https://www.davidmarcus.com/Humor/MathJokes.htm and other versions at https://www.math.utah.edu/~cherk/mathjokes.html
There were two men trying to decide what to do for a living. They went to see a counselor, and he decided that they had good problem solving skills.
He tried a test to narrow the area of specialty. He put each man in a room with a stove, a bucket of water, and an empty pot on the stove. He said, “Boil some water in the pot.” Both men filled the pot with water from the bucket and turned on the burner to boil the water.
Next, he put them into a room with a stove, a bucket of water, and a pot full of water on the stove. Again, he said, “Boil the water in the pot.” The first man immediately turned on the burner. The counselor told him to be an Engineer. The second man emptied the pot and proudly said that now the problem is reduced to the previously solved problem. The counselor told him to be a mathematician.
This version from: https://www.davidmarcus.com/Humor/MathJokes.htm and other versions at https://www.math.utah.edu/~cherk/mathjokes.html
Reply to self: of course, the prime example is counting. If you have five breads, you can sell three, and have two breads left after that.
Similarly, If you have five apples, you can sell three, and have two apples left after that.
You didn’t have to learn separate addition tables for breads, apples, etc.
Instead you learned that all such problems essentially are the same, and you learned how to manipulate the equivalence classes of those (which are called 5, 3, and 2)
Similarly, If you have five apples, you can sell three, and have two apples left after that.
You didn’t have to learn separate addition tables for breads, apples, etc.
Instead you learned that all such problems essentially are the same, and you learned how to manipulate the equivalence classes of those (which are called 5, 3, and 2)
I don't think your examples are examples of solving a different problem.
Agree with this. And I guess a more “applied” branch of science that covers this would be Computer Science in the area of Computational Complexity (https://en.m.wikipedia.org/wiki/Computational_complexity_the...)
See for example the section on Complexity classes wrt the P/NP/Pspace class problems mentioned above
See for example the section on Complexity classes wrt the P/NP/Pspace class problems mentioned above
To add to this, another mathematical term to be familiar with is "isomorphism". It quite literally means showing that two structures are the same, and perserve the same binary relations (coming from modern Algebra).
If you can show that domain A is isomorphic to domain B, then all of the things you know how to do for domain A can be trivially applied to domain B. Thinking about solving problems in terms of isomorphisms has been tremendously helpful for my day-to-day problem solving.
If you can show that domain A is isomorphic to domain B, then all of the things you know how to do for domain A can be trivially applied to domain B. Thinking about solving problems in terms of isomorphisms has been tremendously helpful for my day-to-day problem solving.
I love this answer, because it is such a "duh" answer but also so non-obvious (at least for me).
We're taught so much about the mechanics and details about mathematics in school, that I've never taken a step back to understand it from a fundamental/philosophical level for what it is. Beautiful answer.
We're taught so much about the mechanics and details about mathematics in school, that I've never taken a step back to understand it from a fundamental/philosophical level for what it is. Beautiful answer.
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
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 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
2. https://vowpalwabbit.org/
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
2. https://vowpalwabbit.org/
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.
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.
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.
statisticians, electrical engineers, data scientists and physicists will all often use the same math (linear systems) but with very different names attached.
To complete the answer, the field of research interested in solving this kind of problem is called operational research.
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?"
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"
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"
Yes, that's what it made me think of as well. Recently an audible version of the book was released and it's actually pretty well done for a math book
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.)
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.)
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:
MIT 6.890 https://ocw.mit.edu/courses/electrical-engineering-and-compu...
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).
MIT 6.890 https://ocw.mit.edu/courses/electrical-engineering-and-compu...
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.
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).
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).
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/...
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/...
Kept reading the thread to see if anyone would mention conceptual blending.
The Way We Think is not a book I will forget.
The Way We Think is not a book I will forget.
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...
https://en.m.wikipedia.org/wiki/Category_theory
https://open.spotify.com/episode/6v01kNIPZZTmQk483nFy3H?si=8...
Another category theory resource you may find interesting is Category theory for programmers by Bartosz Milewski. He also has a great video course on youtube. If you want a taste of what category theory is, you can checkout his interview on corecursive.
https://github.com/hmemcpy/milewski-ctfp-pdf
https://github.com/hmemcpy/milewski-ctfp-pdf
I think category theory involves mapping mathematical problems from different math domains. For example looking to solve questions like “what problems or equations From topology are similar to problems solved by number theory? And what is the underlying language?”. Could be of interest
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.
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.
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
[1] https://ieeexplore.ieee.org/iel5/32/5010265/05010283.pdf
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]
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.
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.
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.
Edit: Someone ITT also mentioned ILP (integer linear programming). Also a good example. E.g., many optimization programs can be mapped to ILP.
[1] https://en.wikipedia.org/wiki/Turing_reduction
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.
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.
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.
Edit: Someone ITT also mentioned ILP (integer linear programming). Also a good example. E.g., many optimization programs can be mapped to ILP.
[1] https://en.wikipedia.org/wiki/Turing_reduction
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.
There is also TRIZ for Software Engineering. Darrell Mann has worked on applying TRIZ to the Software domain. There is also a book [1] from him, which is not easy to read if you are not familiar with TRIZ.
[1]: https://store.systematic-innovation.com/systematic-software-...
[1]: https://store.systematic-innovation.com/systematic-software-...
> industrial problems
Based on tens of thousands of Russian patents (i.e. problems + solutions).
Used by Samsung and others in modern "innovation", i.e. new patents.
Based on tens of thousands of Russian patents (i.e. problems + solutions).
Used by Samsung and others in modern "innovation", i.e. new patents.
+1 for TRIZ. "Industrial" is maybe a tad too restrictive word though
[deleted]
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
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
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.
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.
Not familiar with Frame Innovation, but you might be interested in Brian Cantrell talking about system architecture. He emphasizes that one can only prioritize so many values at a time, which will tend to drive (and presumably focus) architectural choices and flavor. (Sorry, not in my notes which video, and YT search is not helping.)
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.
In practice this almost always means translating to the formats used by (Mixed) Integer Programming (MIP) solvers, Constraint Programming (CP) solvers or SAT solvers.
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.
In practice this almost always means translating to the formats used by (Mixed) Integer Programming (MIP) solvers, Constraint Programming (CP) solvers or SAT solvers.
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.
And similarly relevant, using a solver independent modelling language like [MiniZinc](https://www.minizinc.org/) means that it is possible to write a model, and then translate it formats suitable for use with MIP, CP, and SAT solvers.
Yes MiniZinc is excellent.
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.
I'm glad you got something out of 'The Algorithm Design Manual'. Alas, I found that book exceedingly fluffy.
Compare http://jeffe.cs.illinois.edu/teaching/algorithms/ perhaps for something more meaty.
Compare http://jeffe.cs.illinois.edu/teaching/algorithms/ perhaps for something more meaty.
From “The Origin of Consciousness in the Breakdown of the Bicameral Mind”:
“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.”
“Understanding in science is the feeling of similarity between complicated data and a familiar model.”
“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.”
“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.”
“Understanding in science is the feeling of similarity between complicated data and a familiar model.”
“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.”
"Young man, in mathematics you don't understand things. You just get used to them." - (supposedly) von Neumann
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
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
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!)
(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
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.
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.
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.
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.
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: https://en.wikipedia.org/wiki/Duality_(mathematics)
If you want to be even more general, check out a field of mathematics called category theory (https://en.wikipedia.org/wiki/Category_theory). 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.
If you want to be even more general, check out a field of mathematics called category theory (https://en.wikipedia.org/wiki/Category_theory). 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.
https://en.wikipedia.org/wiki/Analogical_models
https://en.wikipedia.org/wiki/Analogical_models
My favourite example of this is how no limit Texas holdem was solved.
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.
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.
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.
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.
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.
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.
Got a reference for this?
My understanding is Nash equilibrium exists in any game with finite states, regardless of perfect or imperfect information.
The bit about announcing your strategy holds by definition - the equilibrium is defined such that no player can improve, thus it doesn't matter if the other player's strategy is known. Also, I don't think there's a requirement that Nash strategies be reachable by iteration.
My understanding is Nash equilibrium exists in any game with finite states, regardless of perfect or imperfect information.
The bit about announcing your strategy holds by definition - the equilibrium is defined such that no player can improve, thus it doesn't matter if the other player's strategy is known. Also, I don't think there's a requirement that Nash strategies be reachable by iteration.
Everything you said about Nash equilibrium is true, I didn't mean to imply that it can only be found in perfect information games via iteration.
What I wanted to say is that methods for finding it via iteration and self-play exist and are well defined but only for perfect information games.
The research itself is here: https://ai.facebook.com/blog/rebel-a-general-game-playing-ai...
What I wanted to say is that methods for finding it via iteration and self-play exist and are well defined but only for perfect information games.
The research itself is here: https://ai.facebook.com/blog/rebel-a-general-game-playing-ai...
Hey just wanted to say thanks for sharing this.
I believe you could say the minimax strategy to the 2 player game of heads up no limit is solved but beyond that is stretching it.
I am way out of it though. I suspect anything more than 2 players is unsolvable when you factor in the stochastic nature of the drunk guy at the table with more than 2 players. Then based on his play he subtracts or adds EV to us randomly.
I won't even let myself think past this though with poker because IMO it is a waste of time.
I am way out of it though. I suspect anything more than 2 players is unsolvable when you factor in the stochastic nature of the drunk guy at the table with more than 2 players. Then based on his play he subtracts or adds EV to us randomly.
I won't even let myself think past this though with poker because IMO it is a waste of time.
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. https://www.tandfonline.com/doi/full/10.1080/135467808024901...) 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.
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...
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...
Charlie Munger's mental models are particularly famous for applying this technique to make intelligent decisions in life. Many of them are documented here:
https://fs.blog/mental-models/
Another one from System Designers is called an Archetype. Most problems can be reduced to an archetype for understanding and solving effectively. https://thesystemsthinker.com/topics/archetypes/
Another one from System Designers is called an Archetype. Most problems can be reduced to an archetype for understanding and solving effectively. https://thesystemsthinker.com/topics/archetypes/
Category Theory aims to do something like that
[deleted]
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
https://arxiv.org/abs/2009.02133
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.
A borrowable digital copy is at the Internet Archive: https://archive.org/details/bypasses00zdzi
A borrowable digital copy is at the Internet Archive: https://archive.org/details/bypasses00zdzi
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?
How do we map programming to understanding genetic codes?
How do we map psychological research or zoological data to operations research?
How do we map programming to understanding genetic codes?
How do we map psychological research or zoological data to operations research?
One thing that has been worked, at least with genetic codes, is mapping them to linguistics (or rather to text), although it could be argued that the scaffolding of this mapping is still mathematical. I guess in this case the analogy was already there, waiting to be leveraged. Mode info: https://deepmind.com/blog/article/enformer
But we need the people with feet in both doors to make the connections necessary to figure out what mappings can be used, and that seems nontrivial
I have been super into the book Introduction to the Theory of Complex Systems
by Thurner, Hanel, Klimek.
I thought the whole field of Complex Systems was kind of bullshit before this book. IMO we just don't know that much in this area in 2022.
It is just too new and different. I thought it was about fractals or some nonsense before reading this book.
I thought the whole field of Complex Systems was kind of bullshit before this book. IMO we just don't know that much in this area in 2022.
It is just too new and different. I thought it was about fractals or some nonsense before reading this book.
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 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.
https://en.wikipedia.org/wiki/G%C3%B6del_numbering
https://en.wikipedia.org/wiki/G%C3%B6del_numbering
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.
They often start from something unrelated and work towards solving something very different.
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?
What comes to mind is studying Category Theory and Abstract Algebra.
Category Theory really helped me in building a framework for finding similarities in problems. Which, after all, is the basis for creativity in general. Can’t solve a problem if you don’t know what questions to ask in the first place.
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
I thought repeatable techniques. Look into modeling and analytics.
Biomimicry engineering perhaps?
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)
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
Any thoughts or pointers to relevant research would be much appreciated!