For a sequence of accesses to keys in a binary search tree with keys, let be the minimum total cost of serving by any binary search tree algorithm that may rotate the tree, even one that knows in advance. Prove or disprove that splay trees serve every access…
A positive integer is perfect if it equals the sum of its proper divisors, like and . Every known perfect number is even. Is there an odd perfect number?
A sorting network on wires is a fixed sequence of comparators, each of which swaps the values on two wires if they are out of order, such that every possible input comes out sorted. What is the minimum number of comparators in a sorting network for inputs?
Let be the smallest number such that any points in the plane, no three on a line, include points that are the vertices of a convex polygon. Prove or disprove that for every .
Given a real matrix and a vector , decide whether there is with . Is there an algorithm whose number of arithmetic operations is bounded by a polynomial in and alone, independent of the size of the numbers in and ?
Euler's totient counts the integers in that are coprime to . When is prime, , which certainly divides . Is there a composite number for which divides ?
The Riemann zeta function is defined by for and extended by analytic continuation to all complex . It vanishes at . Prove that every other zero of has real part exactly .
Prove that for every positive integer there is a prime number strictly between and .
A Hadamard matrix of order is an matrix with entries whose rows are mutually orthogonal, so that . Such a matrix can exist only if is 1, 2 or a multiple of 4. Prove that a Hadamard matrix exists for every multiple of 4.
Let be the number of times the integer appears in Pascal's triangle. For example, . Is there a constant with for every ?
What is the physical mechanism that produces ball lightning — the luminous, floating, sometimes room-sized spheres of light occasionally reported during thunderstorms — and can it be reliably reproduced in the lab?
Why does life on Earth use almost exclusively 'left-handed' amino acids and 'right-handed' sugars, when the same basic chemistry could in principle work equally well with the mirror-image molecules, and what process originally broke this molecular symmetry?
Under what conditions do large particles sink to the bottom of a shaken granular mixture instead of rising, reversing the usual Brazil-nut effect?
Why do certain sand dunes emit a loud, sustained musical 'booming' or 'singing' hum when sand avalanches down their slip face?
Why does a curling stone curve in the direction it is spinning, when simple friction models predict it should curl the opposite way or not curl at all?
Is there a theoretical model that can predict the statistical structure of turbulent flow (e.g. energy distribution across eddy sizes) directly from the Navier-Stokes equations, without ad hoc empirical closures?
What is the physical nature of the glass transition — why does a liquid cooled fast enough become a rigid amorphous solid with a huge (often 10+ orders of magnitude) slowdown in molecular motion, without any obvious change in structure or a sharp thermodynamic phase transition?
Do isolated magnetic north or south poles (magnetic monopoles) exist as fundamental particles, as predicted by some grand unified theories, or is magnetic charge always found in inseparable north-south pairs as observed so far?
Why do measurements of the universe's current expansion rate (the Hubble constant) using the early universe (cosmic microwave background plus the standard cosmological model) consistently give a lower value (~67-68 km/s/Mpc) than measurements using nearby stars and supernovae (~73 km/s/Mpc)?
What is dark matter actually made of — is it a new fundamental particle (like a WIMP or axion) that barely interacts with ordinary matter, or does the evidence for it instead point to gravity itself working differently than Einstein and Newton predicted on galactic scales?