Exponential Divide and Conquer

OPT(U,s,t) is the length of s and t, and you choose the cheapest.

You split the path into two halves in all possible ways. This is called Exponential Divide and Conquer.



m is an intermediate point.

｜S｜=｜｜U｜/2｜+1


T∪S=U


T∩S=m



n is nodes.

∴

ε>0

The exponential space is huge.


コメント

コメントを投稿

このブログの人気の投稿

The Sylvester-Gallai Theorem

イメージ
The deformation is the mathematical concept. The Sylvester-Gallai Theorem is that a finite set of points in the plane have the proper line through any two of them, and it passes through a third point of the set. Moreover, it must be on the same line. P is the the noncollinear finite set. S(P) is the set of connecting lines in P. p∈P, s∈S(P) p and s are perpendicular, so they are not the ordinary line. (s*,p*) is the smallest distance, and s* is in the ordinary line. l∩P={p} l must be the ordinary line. This is the contradiction. l∩S(P) There is the cyclically intersection points (p,x1). x1,・・・xk is on l. Moreover it crosses S. This must be ordinary. You also see the extra dimensions. i lines are determined by P.
続きを読む

The Quantum Rhythm of the Primes: The Montgomery-Dyson Confluence

The history of mathematics is often viewed as a progression of isolated starlight—brilliant individuals working in silos of abstraction. However, the most profound breakthroughs usually occur when two distant stars collide. The story of Hugh Montgomery and Freeman Dyson is the premier example of such a collision, revealing that the heart of number theory and the chaotic vibrations of the physical world beat to the exact same drum. ​The Abstract Search for Order ​To understand the magnitude of this discovery, one must first look at the prime numbers . Primes are the "atoms" of mathematics, yet they appear along the number line with a frustratingly unpredictable rhythm. In 1859, Bernhard Riemann proposed that the secret to their distribution lay in the zeros of the Riemann Zeta Function . ​Riemann’s Hypothesis suggested these zeros sit on a single critical line. But even if they were on that line, their specific spacing remained a mystery. Were they clumped together like s...
続きを読む

Geometric Infinite Expansion of Squares and the Fractal Model of Prime Creation at the +1 Boundary

イメージ
This paper introduces a geometric framework that defines numbers not as dimensionless points, but as the areas of squares, emphasizing dimension and spatial extension. By modeling the interaction between the infinity of the integer space and the self-similar (fractal) expansion of squares . This is my formula which generate prime numbers. In geometric terms, this formula is rigorously illustrated as follows: 1. Core Formation: A closed square domain of area p^2 , with a side length equal to the prime p. 2. Asymmetric Expansion (Gnomon): Two rectangular domains of width (d−1) and length p, structurally appended to the horizontal and vertical boundaries, denoted by 2p(d−1). This process represents an infinite expansion algorithm wherein the square consumes the external integer space while strictly preserving its own self-similarity. Squares possess the highest structural affinity for fractals due to their capacity for infinite grid-like division and consolidation. As d progr...
続きを読む