# The Algebraic Analog of P vs NP

Mathematicians often isolate themselves within their specialties (the algebraic geometers vs the analysts vs the probabilists vs the theorists and so on). But some of the most brilliant results arise from applying tools from one field to problems in another.

One of the largest open problems in mathematics and computer science is the P vs NP problem. It asks whether a problem whose solution can be checked in polynomial time is actually solvable in polynomial time.  You can learn the basics about P vs NP here. Since the problem was formalized by Stephen Cook in 1971, many people in complexity theory have spent their time trying to make progress on it. So why is P vs NP unsolved? Fundamentally, some people think that the problem cannot be proved or disproved from our standard set of mathematical assumptions (i.e P vs NP might be independent of ZFC and other axiomatic systems). Additionally, several proof techniques have been proven insufficient (specifically relativizing proofs and natural proofs).

(Debatably) The most viable track for progress on P vs NP that’s still on the table (for now, anyway) is actually rooted in algebra! The idea, introduced by Leslie Valiant in 1979, is to study two classes of polynomials, VP and VNP, and see whether they’re equal. (For those whose ears are ringing at that name, this is the same Valiant who would later come up with the “probably approximately correct” PAC learning model.) Many believe that a proof for whether or not VP equals VNP would be a huge step in solving P vs NP.

Advertisements

# How Google Makes Money

How much do a moose’s antlers weigh? Not a moose, but a moose’s antlers. Finding the answer takes less than 10 seconds thanks to our favorite search engine, Google. Even more impressive than how heavy moose antlers are (about 40 pounds or 18 kg: thanks, Google) is that we can find the answer to this, or almost any other question, for free. In 2015, Google’s parent company, Alphabet, posted over 75 billion dollars in revenue and is projected to bring in over 80 billion dollars in revenue in 2016. Google brings in approximately 99% of Alphabet’s total revenue; so Google makes a ton of money. Yet a large portion of Google’s products are free to users. How does a company so integrated into our society, producing so much revenue, not charge its users? Easy, ads. Continue reading

# What’s up with the Graph Laplacian?

This is a guest post written by my friend, Jeremy Kun! He’s the author of the popular blog Math ∩ Programming, your go-to site for learning about algorithms, machine learning, cryptography, and so much more.

There’s a deep connection in mathematics between a graph (a set of vertices and edges), and the algebraic properties of special matrices associated with that graph.

Here’s the simplest example of this phenomenon. Say you take an undirected graph $G = (V, E)$ and you let $A = (a_{i,j})$ be its adjacency matrix, where $a_{i,j} = 1$ if $(i,j) \in E$ is an edge, and $a_{i,j} = 0$ otherwise. The matrix $A$ is an $n \times n$ square matrix with $n = |V|$. The remarkable fact is that the $i,j$ entry of $A^k$ contains the number of walks of length $k$ from $i$ to $j$. In this example, the cube of the adjacency matrix counts the number of length-3 walks (paths where you can repeat vertices/edges) between all pairs of nodes. So there is one walk from 5 to 3, and four walks from 1 to 4.

# The Sprague-Grundy Theorem

The overall goal of this post is to prove that every impartial game is equivalent to a game of nim. While this result is often called the Sprague-Grundy theorem, the theorem doesn’t actually say anything about this conclusion. After proving the theorem, I’ll explain why a game’s equivalence to nim immediately follows.

# Nim

Nim is a simple game, in which 2 players take turns removing objects from piles until there are no more objects left. This post will define basic terms for combinatorial game theory, detail the rules of nim, and explain how to win the game.