P vs NP vs PSPACE: Understanding Computational Complexity

Introduction: Why Do We Care About Complexity?

Computer science problems are usually categorized as easy or difficult according to how much computational effort is needed to solve them. In this light, complexity theory can be used to categorize problems based on the resources needed by drafted algorithms. Space and time are the two most important resources to consider. Time refers to the amount of computational work an algorithm takes to finish as the input size increases, while space refers to the amount of memory an algorithm needs while it runs as the input size increases. A problem that can be solved efficiently using a reasonable amount of time and memory is generally considered manageable, while problems requiring vast amounts of computational resources may become impractical for modern computers to solve.

What is P?

P stands for Polynomial Time. It is a class of problems that can be solved by a conventional computer in a reasonable length of time. More formally, a problem belongs to the P class if there exists an algorithm that can solve it in polynomial time, meaning its execution time can be expressed as O(nᵏ), where n represents the size of the input and k is a fixed constant.

An example of this is sorting a list of numbers. The idea of polynomial time is important as it describes problems whose difficulty does not grow rapidly as the input increases. Efficient sorting algorithms are available that can sort items in approximately O(n log n) time.

Simply put, polynomial-time algorithms are considered efficiently solvable when compared with exponential-time algorithms such as O(2ⁿ). For example, if the input doubles, a polynomial-time (O(n²)) algorithm becomes about four times the cost, whereas an exponential algorithm can become drastically more expensive.

Therefore, P represents problems for which we have efficient algorithms that can actually find their solutions, thus making P one of the fundamental complexity classes in computer science.

What is NP?

NP (Nondeterministic Polynomial Time) is a class of problems whose solutions, like those of the P class, can be verified efficiently, though finding those solutions MAY be difficult.

For example, reconsidering the problem of sorting a list: if someone provides the list as a proposed solution, we can verify it efficiently by comparing each pair of neighbouring elements. This takes polynomial time.

At this juncture, it becomes important to distinguish between finding a solution to a problem and verifying the solution to the problem. Finding a solution may require trying many possibilities, while verifying a given solution could be much easier. Therefore, NP problems do not necessarily mean a given problem is difficult (or impossible) to solve; it means their solutions can be verified efficiently.

P vs NP: The Big Question

The P = NP? question is a very famous one in computer science. It asks whether every algorithm whose solution can be verified quickly can also have its solution found quickly. Algorithms in P can be solved efficiently, while algorithms in NP have solutions that can be verified efficiently. So since all that can be solved quickly can also be verified quickly, it means that P is a subset of NP (P ⊆ NP). However, nobody has actually been able to prove whether P and NP are equal or different.

The question is very important as its answer directly ties to major consequences for fields such as mathematics, cryptography, optimization, AI and computer science.

Another important concept here is the NP-complete problems. These are problems that are both in NP and at least as difficult as every other problem in NP. Even for one NP-complete problem, if an efficient polynomial-time algorithm were discovered for it, it would prove that P = NP.

What is PSPACE?

PSPACE stands for Polynomial Space. It refers to the special class of problems that can be solved by using an amount of memory that grows polynomially as the size of the input increases. In other words, PSPACE is more concerned with how much memory a computer requires to solve a given algorithm, rather than focusing on how long the computation takes.

As an example, let’s take a computer solving a chess game by exploring many possible moves. There is an enormous number of possible paths to take for each piece, meaning the computer could spend an extremely long time examining them. A point worthy of noting is that it may not store all those paths at once. It could just explore one path, then keep track of the necessary information, and then reuse that memory when exploring another path. If the amount of memory it requires begins to grow polynomially with each input, then the problem belongs to PSPACE. In this light, PSPACE does not necessarily mean a problem can be solved quickly; rather, a problem may take an extremely long time to solve while still requiring only a polynomial amount of memory.

How Are P, NP, and PSPACE Related?

The three classes are related by the statement: P ⊆ NP ⊆ PSPACE. This simply means that every problem in P is also in NP, and any problem in NP is also in PSPACE.

P ⊆ NP: This states that if an algorithm can be solved quickly, then it means its solutions can also be verified quickly. Therefore, every problem in P is also in NP.

NP ⊆ PSPACE: In here, if a solution can be verified in polynomial time, then the verification process can be done using polynomial memory. So every problem in NP is also in PSPACE.

P ⊆ PSPACE: Since P is contained in NP, and NP is contained in PSPACE, that means P is also contained in PSPACE.

A good point to note is that we do not know for sure whether P = NP or if NP = PSPACE, but determining these relationships is a major goal of computational complexity theory.

Why Witnesses Matter

A witness is a piece of information that shows that a particular problem has a valid solution. The witness does not necessarily have to be easy to discover; the main point is that once provided, it can be checked efficiently.

For example, suppose you claim that a particular number is the solution to a mathematical equation. The number itself can serve as the witness here. A verifier then can take that number and perform a simple calculation to determine if it satisfies the required conditions.

This again brings to the point the difference between finding and verifying. Finding a solution may require searching through a large range of possible answers, but verifying a solution that has been provided can be much faster since the solution has “already” been found.

This is exactly where NP comes in. Problems in NP have witnesses that can be verified in polynomial time. Zero-knowledge proofs take this idea further: a prover can demonstrate knowledge of a valid witness without revealing the witness itself. This allows the verifier to become convinced that the statement is true, while the underlying secret is kept private.

From NP to Zero-Knowledge Proofs

In NP, a witness is information that demonstrates that a particular statement is true. In normal circumstances, a prover could just give the witness to the verifier who would then check it efficiently. But what if there is sensitive information that the prover does not want to reveal?

This leads to the idea of zero-knowledge proofs: a prover can convince a verifier that they know a valid witness without revealing the witness itself. The verifier becomes convinced that the statement is true, without knowing anything about the secret information.

As an example, imagine proving that you know the password to an account without actually telling someone the password. A ZK protocol allows you to demonstrate knowledge of the password without revealing it.

The relationship between NP and ZK is important because many ZK systems are designed to prove the correctness of statements that can be expressed in NP form. Understanding P, NP, witness, and verification therefore provides a strong foundation for understanding how modern ZK systems function.