- Some abstract solution A can solve some concrete problem X.
- This is self-evident if you know A
- But sometimes a surprising problem Y can be solved with A
- There exists a certain problem transformation B that maps some problems to others.
- maximum flow minimum cut theorem and
- This maps Y, which at first glance is not included in A, to Y’, which is included in A.
What else could be in the problem conversion?
- Solving a problem represented by a vector by transforming it into a complex number vector complex transformation.
- Exchange of value range and definition range
- Consider a set of numbers as a sequence of 0/1’s and use [Fennic tree
- coordinate compression to set the value in the computable range
- DP a huge integer as a sequence of digits Digit DP.
- Attribute Project Selection Problem to [least-cost current
- Consider a number series problem as a [formal power series
This page is auto-translated from /nishio/問題変換 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.