An overview of one of the most important unsolved problems in theoretical computer science and mathematics — Informally, P vs. NP asks whether problems whose solutions can be rapidly verified can also be rapidly solved. Since the early 1970s, when researchers Stephen Cook [1] and Leonid Levin [5] first formally described the problem, P vs. NP has held a place of deep significance in the world of…

If every rectangular tile has at least one side of integer length, must the tiled rectangle also have at least one integer-length side? — Tiling, or tessellation, problems ask if/how a surface can be completely covered by non-overlapping tiles. The study of tilings has yielded many important results, both in pure math and for real-world applications. Examples include the Four Color Theorem, the characterization of tiling patterns with group theory, algorithms in unsupervised machine…

…and it was invented in 1882. — Anyone using a basic shortwave radio during the Cold War might have come across strange stations that almost exclusively broadcasted lists of numbers. One famous such station would briefly play an English folk song called “The Lincolnshire Poacher”, then would rattle off a series of five-digit-long groups of integers. These…

If everyone in a city has exactly one friend in common with every other resident, must there be someone who is friends with all residents? — In order to answer this question, let’s first convert it into the language of graph theory. We represent the people in the city with vertices, and connect any two of these vertices with an edge if they are friends. The degree of a vertex is the number of edges which…

How a mathematician’s time in a forced labor camp during WW2 led to the discovery of a graph theory problem that remains unsolved to this day — In 1944, at the height of World War Two, the Hungarian Jewish mathematician Pál Turán was forced to labor in a brick factory near Budapest. His job consisted of pushing brick-filled carts from kilns to the yards where the bricks were stored. The carts traveled on crisscrossing rails connecting the…

We discuss a range of integer factorization algorithms that can run on classical computers and explore their future in the face of Shor’s algorithm. — Public-key cryptosystems like RSA have become indispensable in the digital age. From helping to secure e-commerce, to ensuring private communication on messaging apps, they constitute critical internet infrastructure. RSA’s power relies on the difficulty of factoring large integers. Other public-key cryptosystems depend on related challenges, like the discrete logarithm problem…

Delving into a deceptively simple-sounding problem that has gone unsolved for decades. — Introduction Like many great questions in math, the Cycle Double Cover Conjecture (C.D.C.C.) has the distinction of being relatively easy to state, but quite difficult to prove. It was proposed independently by two mathematicians, George Szekeres [7] and Paul Seymour [6], in the 1970s. …