Recently, Scott Aaronson posted in his blog 2 nice, teaser posts about Computational Complexity Theory.
In his first post, Scott discusses 2 papers. One paper by Lenny Susskind proposes that the number of elementary operations in a quantum circuit be used as a clock, to measure time intervals. The second paper by Terry Tao uses complexity theory to study the solutions of the Navier Stokes equation.
In his second post, Scott tries to explain to the non-specialist why he believes that .
I know next to nothing about complexity theory, so you better take anything I say next with a grain of salt.
= problems that can be verified in poly time.
= problems that can be solved in poly time. . problems are the easiest to solve problems in .
and are both subsets of . They are believed to be disjoint.
. problems are the hardest to solve problems in but their solution can be verified in poly time. 3-SAT problem is an element of .
If and intersect, then they become equal to each other and to the whole set. This doomsday scenario is called .
In one of his posts, Scott compares the boundary between sets and to an “electrified fence” for electrocuting frogs. Raoul Ohio observes in the comments that the , separation reminds him of the phenomenon of “eigenvalue avoidance”, wherein a random matrix rarely has two degenerate eigenvalues. Raoul’s comment moved me to tears and inspired me to write the following very sad tale.
The Sad Tale Of The Two Sets That Once Kissed and Then Parted
Matrix had two eigenvalues and where . Let
Originally, everyone thought that there was no symmetry in the system that described, which meant that and did not intersect.
Then someone discovered an “accidental” symmetry that led to an “accidental degeneracy”, which led the two sets to kiss at a single point.
Then someone realized that the original model was too naive and that in real life there is a perturbation that breaks the accidental symmetry, so an eigenvalue “gap” develops, which led the two sets to stop kissing each other and part forever.