Live data from Hacker News

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

news.ycombinator.com

31–40 of 81 posts

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

#31
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/...

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

#32
post #5

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

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.

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

#33
post #32
post #5

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

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 ba…

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.

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

#34
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"

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

#35
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)

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

#36
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/

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

#37
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

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

#40
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.
Post reply on HN