Beyond P vs. NP: Finding Harder Problems

The P vs. NP problem#

The discussion on hard programming problems is mostly centered around the famous $\text{P}$ vs. $\text{NP}$ problem. Where $\text{P}$ is the collection of problems that are efficiently solvableWe consider a problem to be efficiently solvable if its running time is bounded by some polynomial., and $\text{NP}$ is the collection of problems that are efficiently verifiableA problem is efficiently verifiable if there’s a way to verify that a given solution is a valid solution of a given problem instance in polynomial time..

The $\text{P}$ vs. $\text{NP}$ problem asks whether these two collections are the same!

The answer to this problem is unknown, as of now. If the answer turns out to be in the affirmative, the two notions (efficient verifiability and efficient search for solutions) would be provably the same. This does not seem very likely, and most researchers believe that it is not the case. There are some exceptions, however, Donald Knuth being the most notableSee the answer to question 17 at https://www.informit.com/articles/article.aspx?p=2213858.. Settling this question might be one way to earn your first million dollars“P vs NP.” n.d. Clay Mathematics Institute.

We can easily establish that any problem in $\text{NP}$ can be solved in exponential time.

We’ll prove in this blog that there are even harder problems than the ones in $\text{NP}$.

The Hardest of Them All#

We’ll answer this question in this blog. As a sneak peek, our answer will be “There’s no such problem.” That is, given any hard problem, we can always find a harder problem—so there’s no hardest problem! This is where we will need to go beyond the the P vs. NP question into the realm of the time hierarchy theorem.

Setting up the Framework#

We’ll limit ourselves to the standard framework of computability theory, conveniently adapted for the general computer science audience we laid down in an earlier blog about the halting problem.

In summary:

• All of our problems will be decision problems. That is, we’ll be interested in deciding whether a given input satisfies certain conditions or not. For instance, the problem of determining whether a given number is prime, or the problem of determining whether a given graph has a HamiltonianA cycle that contains all vertices of the graph. cycle.

• All of our programs will take only one input and return a boolean value. We can easily modify every program to receive only one input by using, for instance, some aggregate data type.

Justifications for why these assumptions do not affect the generality are given in the above mentioned blog.

We’d also assume that we have access to a program $U$ that can simulate a given program for a specified number of steps. Think of it as a modified interpreter that increments a counter after executing each step. We can build it, or modify one, without too much difficulty.

Time Hierarchy Theorem#

We’ll start by introducing the time hierarchy theorem, that’s the key to answering the questions we’ve set out to answer. It basically formalizes and justifies the intuitive notion that given more time, more complex problems can be solved!

We’ll state and prove a weak version of the time hierarchy theorem since it’s easier to prove, and can serve as the foundation of studying the stronger version for interested learners.

The Statement of the Theorem#

In order to avoid weird functions, let’s restrict ourselves to increasing functions $f(n)$ on natural numbers1, 2, 3, … that are computable—that is, there is a program that takes $n$ as input, and outputs $f(n)$. Note that the functions we commonly see in computer science, like $\lg n, n, n\lg{n}, n^2, 5n^3+2n-3, 2^n$, etc., satisfy this condition.

We’ll show that for any such function $f$, there is a problem $A$ that cannot be solved in $f(n)$ time.

This would immediately imply that no matter how much time is given, there’d still be problems that can’t be solved in that time!

There’s a stronger version of this theorem of a more applied flavor that measures the time complexity of the program that solves $A$. However, we’ll restrict ourselves to this weaker version, as it’s more suitable to the blog format.

Defining the Problem in Terms of the Solution#

The approach we’ve taken for coming up with this problem $A$ is a little unusual—instead of defining $A$ directly, we’ll define it in terms of a program $D$ that solves it.

$A$ is the set of all inputs on which $D$ would return TRUE.

Don’t be put off by it as it’s a perfectly legitimate way of defining a problem. For example, we can legitimately define even numbers by first providing a program that tests if a number is a multiple of two, and then say even numbers are all those numbers on which this program returns TRUE.

Designing DDD: The High-Level Idea#

Recall that we’re dealing with decision problems in computability theory where problems are sets. We’ll design $D$ so that it differs from any program that runs in $f(n)$ time on at least one input. This would establish that $A$, the problem solved by $D$, is different from any problem that can be solved in $f(n)$ time.

To be more precise, let’s assume $Q_1, Q_2, Q_3, \ldots$ are all the programs that halt and return an answer in $f(n)$ time. If $A$ could be solved in $f(n)$ time, then surely one of the $Q_i$ from this list would solve it.

We’ll design $D$ in such a way that for any program $Q_k$ from this list, there’s an input $w$ on which $Q_k(w) \neq D(w)$.

While designing $D$, we’ll choose $w$ to be the program $Q_k$ itself!

As $A$ is defined using $D$, this would prove that $A$ can’t be the same as any of the problems solved by the $Q_i$. This would immediately imply that the problem $A$ can’t be solved in $f(n)$ time, as the list of $Q_i$ contains all problems solvable in $f(n)$ time.

This is diagonalization in action that we used to show that the halting problem is unsolvable.

The program DDD#

We’ll define $D$ as follows: $D$ takes an input $w$ and returns TRUE or FALSE. Recall that our problem $A$ is the set of all inputs on which $D$ returns TRUE.

$D$ performs the following steps on the input $w$:

1. $D$ verifies whether $w$ is a valid program. If it isn’t, $D$ returns FALSE. This can easily be done by embedding a compiler of whichever language is chosen in $D$ as a subroutine and calling it on $w$. Let’s refer to the program that $w$ corresponds to as $Q$.

2. $D$ now runs $Q$ on $w$ for $f(n)$ steps, using the program $U$ described earlier. $D$ returns FALSE if the program $U$ does not produce a valid return value (TRUE or FALSE) in this much time.

   Do note that $D$ runs the program $Q$ on itself, as $w = Q$.

3. When $Q$ halts with a valid return value in $f(n)$ steps, $D$ returns the opposite of what $Q$ has returned. That is, if $Q$ returns TRUE, $D$ returns FALSE, and if $Q$ returns FALSE, $D$ returns TRUE.

   Note that by differing with $Q$ on input $w$, $D$ has made sure that $A$ is different from the problem solved by $Q$.

This completes the construction of $D$.

In the above figure, each entry of the table represents the result of running the program $Q_k$ on input $Q_k$ for $f(n)$ steps inside $D$. The problem $A$ is then defined to be the set of all programs $Q_j$ that return FALSE on input $Q_j$, as these are the only inputs on which $D$ returns TRUE.

Just Defining DDD Is Enough#

As the input to $D$ can be any string, it could be given any program whatsoever as an input. In particular, all programs in the chosen language that run in $f(n)$ times can be given as inputs to $D$.

Keep in mind that we are not going to run $D$ to do anything, our job is done by just writing $D$, as this gives us the definition of $A$.

To reiterate, by ensuring that $D$ is different on at least one input from any program that runs and produces a valid result in $f(n)$ time, we have established that $A$ can’t be solved in $f(n)$ time. This is precisely what we set out to do!

We can use this version of the time hierarchy theorem to show that there are problems that can’t be solved in even $2^n, 2^{2^n}, 2^{2^{2^n}},$ or $2^{2^{\cdot^{\cdot^{\cdot^{2^n}}}}}$ time, for example!

Concluding Thoughts#

A stronger version of the time hierarchy theorem can be proven if we measure the complexity of the program $D$ more precisely. We can do so if we make certain assumptions, like the following:

• $f(n)$ is at least $n$. $D$ needs at least this much time to determine $n$ from the input $w$, as $n = |w|$.

• Each step of the simulation takes some constant time. This is a reasonable assumption, as a simulation of one step of the program should not depend on input length.

• Each increment to the counter in $U$ (to check if we have not exceeded $f(n)$ steps) does not take more than $O(\lg f(n))$ time. This is also a fair assumption, as we do not require more than $\lg f(n)$ bits to write down $f(n)$.

The time complexity of $D$ then turns out to be $O(f(n) \lg f(n))$ (simulation of $f(n)$ steps each requiring $O(\lg f(n))$ time). This is under the assumption that the compiler does not need more than this much time to verify if the input $w$ is a valid program.

Once we have this, we can make stronger claims like the following:

There’s a problem that can be solved in $O(f(n) \lg f(n))$ time that can’t be solved in $f(n)$ time.

An obvious and immediate consequence is that

$$\text{P} \neq \text{EXPTIME}$$

where $\text{P}$ is the collection of efficiently solvable problems discussed earlier, and $\text{EXPTIME}$ is the collection of all problems that can be solved in exponential time.

This won’t earn us a million dollars, but it’s no less valuable since there’s a severe dearth of specific results like this in complexity theory. Understanding the nuances of time complexity and the time hierarchy theorem gives you a foundational basis for grappling with the complexities of the ‘P vs NP’ problem.