List of Difficult Math Problems
Recommended post: 【Modern Mathematics】 Modern Mathematics Table of Contents
1. Unsolved difficult problems
a. List of Math Exploration Topics
1. Unsolved Difficult Problems
⑴ Wikipedia List of Unsolved Problems
⑵ 3n+1 Problem: Prove that when transforming a number n by dividing by 2 if it is even, and transforming to 3n+1 if it is odd, this sequence eventually converges to 1
⑶ P vs NP Problem
① Terminology
○ Deterministic algorithm: An algorithm that considers only one possibility at each step of computation
○ Nondeterministic algorithm: An algorithm that considers two or more possibilities at each step of computation
○ A nondeterministic algorithm is a theoretical concept and cannot be implemented on an actual computer
○ It can consider multiple possible paths simultaneously at each step, and assumes that it “luckily” chooses the correct path among them
○ You can think of an adventurer using a cloning technique at each step to search for the optimal path (ref)
○ Therefore, even if the adventurer does not have the ability to clone, if at each point someone gives a hint about which way to go and the hint can be verified, one can similarly search for the optimal path
○ Therefore, a nondeterministic algorithm can be said to be equivalent to a deterministic algorithm that verifies some hint in polynomial time
○ P problems: = Problems that can be solved in polynomial time by a deterministic algorithm
○ Interpreting “could not solve the problem” as meaning “cannot be solved in polynomial time by a deterministic algorithm”
○ NP problems: = Problems that can be solved in polynomial time by a nondeterministic algorithm = Problems that can be verified in polynomial time by a deterministic algorithm
○ NP-hard: Problems to which every problem in NP is polynomial-time many-one reducible to another problem
○ It can be said to be a problem made harder than NP problems
○ NP-complete(NP complete): The set of problems such that problem A is in NP, and at the same time every problem in NP is polynomial-time many-one reducible to it.
② Definition
○ Since deterministic algorithms ⊂ nondeterministic algorithms (e.g., one correct choice and one random choice at each step), it follows that P problems ⊂ NP problems
○ The P vs NP problem must prove whether NP problems are identical to P problems, have more elements, or even whether that cannot be proven
○ NP problems = (P problems) + (NP-complete problems) + (NP problems that are not NP-complete if P≠NP)
Figure 1. P vs NP Problem
③ Examples
○ Shortest path problem between two cities: P problem. Solved by Dijkstra, Floyd Algorithm, etc.
○ Greatest common divisor computation problem: P problem. Solved by the Euclidean algorithm
○ Sorting problem: P problem. Solved by bubble sort, quick sort, etc.
○ Prime factorization: It has not been proven whether it is NP-complete, not NP-complete, or unprovable
○ Traveling salesman problem (TSP, traveling salesman problem): NP-complete problem. Given multiple cities and the distances between each pair of cities, find the shortest route that visits every city exactly once and returns to the starting city
○ Fragment orientation problem (FOP): NP-complete. In bioinformatics, the problem of correctly determining the orientation of DNA fragments
○ Super Mario Bros: NP-hard
○ RNA secondary structure prediction problem allowing pseudoknots or long-range constraints: NP-complete or NP-hard.
○ Finding a subset that is both maximally spread out and maximally informative: NP-hard
⑷ Riemann Hypothesis
⑸ Triangulation Orchard Problem
⑹ Mathematical formula that explains the number of structural isomers of alkanes (ref)
⑺ kissing number: What is the maximum kissing number that an n-dimensional sphere can have in (n + 1)-dimensional Euclidean space? AlphaEvolve derived a better solution in 11 dimensions.
⑻ Brown number: Do there exist natural-number pairs (n, m) such that $n! + 1 = m^2$ other than (4, 5), (5, 11), and (7, 71)?
⑼ Theory on power towers: Despite multifaceted efforts, we know very little about this function (‘Euler’)
⑽ Erdős’ minimum overlap problem
① Problem: Partition the set {$1,2,\ldots,2n$} into two sets $A$ and $B$ of equal size $n$. For each integer $k$, define $M_k=$＃{$(a_i,b_j): a_i\in A,\ b_j\in B,\ a_i-b_j=k$}, the number of pairs whose difference equals $k$. For a given partition $(A,B)$, consider $\max_k M_k,$ the maximum overlap over all differences. Define $M(n)=\min_{A,B}\max_k M_k.$ The constant of interest is $c=\lim_{n\to\infty}\frac{M(n)}{n},$ and the goal is to tighten the best known lower and upper bounds on $c$.
② Recent Result: According to a recent paper (TTT-Discover), the current bound is $0.379005 < c < 0.380876.$
2. Solved Difficult Problems
⑴ Fermat’s Last Theorem: Proven by Professor Andrew Wiles
⑵ Poincaré Conjecture
⑶ Read Conjecture
① A combinatorics problem proposed in 1968 by British mathematician Ronald Read
② The conjecture that the absolute values of the coefficients of a chromatic polynomial can increase and then decrease, but cannot decrease and then increase
③ A chromatic polynomial is an expression that represents the number of ways to color a graph using at most n colors so that adjacent vertices are colored different colors
⑷ Rota Conjecture
① A problem proposed in 1971 by American mathematician Gian-Carlo Rota by generalizing the Read conjecture
② Expands the scope to a general setting that includes not only graphs from the Read conjecture but also the characteristic polynomials of finite sets in vector spaces
① What is the area of the largest sofa that can be moved through an L-shaped bent corridor? The shape of the sofa can be chosen freely.
② Proven in November 2024 by Korean researcher Baek Jineon: Still under verification
⑹ Pancake sorting problem: Proven by Bill Gates
Input: 2022.07.07 01:32