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

  • Posted 2 years ago by piotrgrudzien
  • 160 points
Is there a line of research that looks into solving difficult / intractable problems by finding a mapping that expresses them as different problems that we know how to solve?

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!

48 comments

    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..
    Loading..