<story><title>Ask HN: Solving problems by mapping to other problems that we know how to solve</title><text>Is there a line of research that looks into solving difficult &amp;#x2F; intractable problems by finding a mapping that expresses them as different problems that we know how to solve?&lt;p&gt;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)&lt;p&gt;A general solution for a &amp;quot;compiler&amp;quot; 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&lt;p&gt;Any thoughts or pointers to relevant research would be much appreciated!</text></story><parent_chain><item><author>Someone</author><text>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. &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;NP-completeness#NP-complete_problems&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;NP-completeness#NP-complete_pr...&lt;/a&gt;:&lt;p&gt;&lt;i&gt;“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”&lt;/i&gt;&lt;p&gt;As a second example, in combinatorial game theory, the Sprague–Grundy theorem states&lt;p&gt;&lt;i&gt;“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”&lt;/i&gt;&lt;p&gt;(&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Sprague–Grundy_theorem&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Sprague–Grundy_theorem&lt;/a&gt;)&lt;p&gt;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 (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Nimber&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Nimber&lt;/a&gt;) in order to learn how to play them.&lt;p&gt;Doing such mappings, if not trivial, requires creativity, so I think research on the subject would be in the psychology department.&lt;p&gt;Polya, in “How to Solve it” has some discussion on this (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;How_to_Solve_It#Heuristics&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;How_to_Solve_It#Heuristics&lt;/a&gt;)</text></item></parent_chain><comment><author>kevinwang</author><text>Good answer. Seems like a relevant time to post an old math joke:&lt;p&gt;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.&lt;p&gt;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.&lt;p&gt;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.&lt;p&gt;This version from: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.davidmarcus.com&amp;#x2F;Humor&amp;#x2F;MathJokes.htm&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.davidmarcus.com&amp;#x2F;Humor&amp;#x2F;MathJokes.htm&lt;/a&gt; and other versions at &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.math.utah.edu&amp;#x2F;~cherk&amp;#x2F;mathjokes.html&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.math.utah.edu&amp;#x2F;~cherk&amp;#x2F;mathjokes.html&lt;/a&gt;</text></comment>
<story><title>Ask HN: Solving problems by mapping to other problems that we know how to solve</title><text>Is there a line of research that looks into solving difficult &amp;#x2F; intractable problems by finding a mapping that expresses them as different problems that we know how to solve?&lt;p&gt;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)&lt;p&gt;A general solution for a &amp;quot;compiler&amp;quot; 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&lt;p&gt;Any thoughts or pointers to relevant research would be much appreciated!</text></story><parent_chain><item><author>Someone</author><text>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. &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;NP-completeness#NP-complete_problems&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;NP-completeness#NP-complete_pr...&lt;/a&gt;:&lt;p&gt;&lt;i&gt;“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”&lt;/i&gt;&lt;p&gt;As a second example, in combinatorial game theory, the Sprague–Grundy theorem states&lt;p&gt;&lt;i&gt;“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”&lt;/i&gt;&lt;p&gt;(&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Sprague–Grundy_theorem&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Sprague–Grundy_theorem&lt;/a&gt;)&lt;p&gt;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 (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Nimber&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Nimber&lt;/a&gt;) in order to learn how to play them.&lt;p&gt;Doing such mappings, if not trivial, requires creativity, so I think research on the subject would be in the psychology department.&lt;p&gt;Polya, in “How to Solve it” has some discussion on this (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;How_to_Solve_It#Heuristics&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;How_to_Solve_It#Heuristics&lt;/a&gt;)</text></item></parent_chain><comment><author>Msurrow</author><text>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 (&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.m.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Computational_complexity_theory&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.m.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Computational_complexity_the...&lt;/a&gt;)&lt;p&gt;See for example the section on Complexity classes wrt the P&amp;#x2F;NP&amp;#x2F;Pspace class problems mentioned above</text></comment>