Quantum Bayesian Networks

March 14, 2014

P, NP, Sad Tale

Filed under: Uncategorized — rrtucci @ 3:47 am

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 P\neq NP.

I know next to nothing about complexity theory, so you better take anything I say next with a grain of salt.

NP= problems that can be verified in poly time.

P= problems that can be solved in poly time. P\subset NP. P problems are the easiest to solve problems in NP.

P and NPcomplete are both subsets of NP. They are believed to be disjoint.

NPcomplete=NPhard \cap NP. NPcomplete problems are the hardest to solve problems in NP but their solution can be verified in poly time. 3-SAT problem is an element of NPcomplete.

If P and NPcomplete intersect, then they become equal to each other and to the whole NP set. This doomsday scenario is called P=NP.

In one of his posts, Scott compares the boundary between sets P and NPcomplete to an “electrified fence” for electrocuting frogs. Raoul Ohio observes in the comments that the P, NPcomplete 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 M(t) had two eigenvalues x_1(t) and x_2(t) where t\in[0,1]. Let

Set_1 = \{ (t, x_1(t)) : t\in[0,1]\}
Set_2 = \{ (t, x_2(t)) : t\in[0,1]\}

Originally, everyone thought that there was no symmetry in the system that M(t) described, which meant that Set_1 and Set_2 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.





  1. So sad …

    Comment by Quax — March 14, 2014 @ 5:32 am

  2. OT but this beautiful rant reminded me of your writing style. Thought you may get a kick out of it.

    Comment by Quax — March 22, 2014 @ 2:13 pm

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Blog at WordPress.com.

%d bloggers like this: