Live data from Hacker News

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

news.ycombinator.com

21–30 of 81 posts

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

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

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

#23
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...

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

#24

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.

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

#26
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.

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

#27
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.

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

#28
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...

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

#29

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

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

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

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

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