Skip to content

P < NP In Our Stockings?

December 24, 2020


Brute force wins—sometimes

Teespring.com source

Santa Claus is on the way to visit those of us who have been good.

Tonight is Christmas Eve, and we want to thank everyone who has been supporting Ken and me at GLL.

Whether or not you believe in Santa Claus, whether or not you celebrate Xmas, we should agree that this has been some year.

Indeed the the whole Santa Claus issue raises some questions about truth telling. Children are typically told by their parents that Santa is real; tonight you can “watch” his progress as he travels around the world. Dr. Anthony Fauci even said he traveled to the North Pole to give Santa the new Covid-19 vaccine.

This raises some objections to presenting Santa Claus as a real person, rather than a story:

  • That lying is normally bad.

  • That parents intentionally lying to their children promotes distrust.

  • That it promotes selfishness, greed, and materialism.

  • That it associates good behavior with being materially rewarded with presents from Santa Claus.

  • That tricking children into believing falsehoods interferes with the development of critical thinking.

Most agree that it is harmless, but see this for more on the controversy. Ken finessed it by “superposing” the real Saint Nicholas on what told his children.

Or read this book on The Indisputable Existence of Santa Claus: The Mathematics of Christmas by Hannah Fry and Thomas Evans.

P {\neq} NP

The belief that P is weaker than NP, that there is no efficient algorithm for many problems, is perhaps our version of Santa Claus. We cannot prove it, we cannot see how to even really approach it.

But most of us believe that a resolution is presently out there, and that says there is no efficient algorithm for SAT and other NP-complete problems. Is this a story we tell each other like Santa Claus: Is P{<}NP the same? Is it just a story we tell each other?

P {=} NP

Well not really: P is not equal to NP yet. But there are many important examples of hard problems that are solved every day. These problems are solved even though they are believed to be hard to solve.

The algorithms that are used are brute force. The algorithms just try all the possible solutions and keep checking to see if this guess is correct. While complexity theory is filled with clever algorithms for hard problems that:

  • Solve special cases;

  • Give approximation solutions;

  • Solve some of the time;

  • And so on.

Often only a perfect solution in the general case is what we sometimes needed. Two important examples of this are:

  1. Bitcoin mining;

  2. Password cracking.

The first of these can be as precious as a diamond, but the latter is a lump of coal when it happens to us.

Password Cracking

A password is checked by a system by using a password file {\mathsf{P}} that consists of records like

\displaystyle  [name, h(name,p)].

A user who claims to be {name}, then proves this by giving an {w} so that

\displaystyle  h(name,w) = h(name,p).

Here {h(x)} is hash function. This function is public and so is the file {\mathsf{P}}. Well the file is not exactly public, but an attacker often does know the file. Note, the value {name} represents the name and other information that is used like salt.

The hope is that it is hard to invert the hash function {h(x)} and so an attacker cannot easily find a {w}. The difficulty is that a brute force attack works when {p} can be guessed. And this unfortunately is quite often. If we think Bob used the password “12345678,” then

\displaystyle  h(Bob,12345678)

will check correctly.

Even with random passwords cracking them by brute force is possible

Graphics processors can speed up password cracking by a factor of 50 to 100 over general purpose computers for specific hashing algorithms. As of 2011, available commercial products claim the ability to test up to 2,800,000,000 passwords a second on a standard desktop computer using a high-end graphics processor. Such a device can crack a 10 letter single-case password in one day.

This is an amazing result. The algorithm that breaks passwords, the cracker, is just brute force. But the cleverness is all in the implementation. The cleverness is using GPU’s or FPGA’s to make the algorithm—brute force or not—run so fast. Here GPU’s are graphics processors and FPGA‘s are field programmable arrays. Both of these devices are hardware that is well matched to computing the hash functions that are used. See this Hackaday item for details.

Open Problems

Have a safe Xmas, and a safe rest of the year. Take care all.

Dick and Ken.

6 Comments leave one →
  1. Christopher Heckman permalink
    December 24, 2020 8:14 pm

    “These problems are solved even though they are believed to be hard to solve.”

    No. *Single instances* of these problems are solved. If you are only worried about solving one particular instance (or two, or three), your program (if it halts) has running time O(1). It’s only when you want to solve them all (actually, just infinitely many), and there’s a parameter n that varies, that P and NP become relevant.

    For example, the Travelling Salesman Problem on 50 cities can be solved using brute force, and its running time is O(1). Granted, the constant is large (50! * 50 * 3 arithmetic operations ought to do it), but there’s no n to vary, so P and NP are irrelevant.

  2. December 26, 2020 1:15 am

    Isn’t P=NP more like equivalent to the existence of Santa? We keep on looking for an algorithm, but no one has found one (yet).

    • Christopher Heckman permalink
      December 26, 2020 8:31 pm

      The situation might be more complicated; it might be able to prove that there is an algorithm but you can’t explicitly show it. (I doubt that the P=NP algorithm would be like this, though.)

      For instance, take a graph [network] and look at its embeddings in 3-D space. There might be two cycles which in this embedding are two linked simple closed curves, or not. Robertson and Seymour proved that there is an algorithm to determine whether this is the case, but (the last time I checked up on it) no one had actually produced an explicit algorithm. Furthermore, the RS algorithm runs in less than cubic (O(N^3)) time, so it’s even efficient!

      (Very brief explanation: They showed that the set of solutions is “minor closed”, and that there is a finite set of graphs such that any “linked embedding” contains one of them as a minor, so you just test your graph to see if it contains one of these graphs. There’s a similar algorithm for planarity, where the set contains the two elements K(5) and K(3,3).)

    • javaid aslam permalink
      December 30, 2020 9:28 pm

      Is there anyone really looking for Santa Claus?

  3. William Haeberlin permalink
    December 26, 2020 6:04 pm

    Sounds like the great vaccine anti vaccine debate to me. If p equaled np you could simply tell people to stop being stupid.

  4. funny permalink
    January 1, 2021 3:46 am

    Open problem ‘Have a safe Xmas, and a safe rest of the year. Take care all.’.

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