“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)

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

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)

See for example the section on Complexity classes wrt the P/NP/Pspace class problems mentioned above

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.

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.

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

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/

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.

statisticians, electrical engineers, data scientists and physicists will all often use the same math (linear systems) but with very different names attached.

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

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

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

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

The Way We Think is not a book I will forget.

https://en.m.wikipedia.org/wiki/Category_theory

https://open.spotify.com/episode/6v01kNIPZZTmQk483nFy3H?si=8...

https://github.com/hmemcpy/milewski-ctfp-pdf

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.

[1] https://ieeexplore.ieee.org/iel5/32/5010265/05010283.pdf

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

[1]: https://store.systematic-innovation.com/systematic-software-...

Based on tens of thousands of Russian patents (i.e. problems + solutions).

Used by Samsung and others in modern "innovation", i.e. new patents.

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

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.

Compare http://jeffe.cs.illinois.edu/teaching/algorithms/ perhaps for something more meaty.

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

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

(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!)

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.

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.

https://en.wikipedia.org/wiki/Analogical_models

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.

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.

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

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.

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

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/

https://arxiv.org/abs/2009.02133

A borrowable digital copy is at the Internet Archive: https://archive.org/details/bypasses00zdzi

How do we map programming to understanding genetic codes?

How do we map psychological research or zoological data to operations research?

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.

https://en.wikipedia.org/wiki/G%C3%B6del_numbering

They often start from something unrelated and work towards solving something very different.