Computer science is often associated with writing code, building applications, and designing systems. But underneath all modern technology lies a deeper layer of theoretical questions about what computers can actually compute and how efficiently problems can be solved.

For decades, researchers have explored the limits of computation, discovering that some problems are extremely difficult while others may be fundamentally impossible to solve. These questions are not just academic. They influence fields like cryptography, artificial intelligence, optimization, and software verification.

The P vs NP problem is widely considered the most important open problem in theoretical computer science. At its core, the question asks: if a problem's solution can be verified quickly, can it also be solved quickly? To explore this question, computer scientists divide computational problems into complexity classes. P (Polynomial time) Problems that can be solved efficiently by an algorithm.

• sorting a list;
• finding the shortest path in a graph;
• basic arithmetic operations.

NP (Nondeterministic Polynomial time) Problems for which a proposed solution can be verified quickly, even if finding that solution may be difficult, belong to the NP class. A classic example is Sudoku. Checking whether a completed puzzle is correct is easy, but solving the puzzle from scratch may take much longer. The big question behind the P vs NP problem is whether these two classes are actually the same. If P = NP, it would mean that many problems currently considered extremely difficult could be solved efficiently. This would have enormous consequences for fields like:

• cryptography;
• logistics;
• scheduling;
• machine learning.

Modern encryption systems rely on certain problems being computationally hard. If P = NP were proven, many cryptographic systems could potentially be broken. Because of its importance, the Clay Mathematics Institute listed P vs NP as one of the Millennium Prize Problems, offering $1 million for a correct proof. Despite decades of research, the question remains unanswered.

In 1936, Alan Turing showed that some problems cannot be solved by any algorithm. One of the most famous examples is the Halting Problem, which concerns determining whether a program will eventually stop running or continue forever for a given input.

At first, this may seem solvable. One could imagine creating a program that analyzes other programs and predicts their behavior. Suppose such a program exists, called HaltChecker. This program takes another program as input and reports whether it halts or runs forever. Turing showed that assuming the existence of such a program leads to a contradiction. Imagine writing another program that uses HaltChecker and deliberately does the opposite of its prediction:

• If HaltChecker says the program halts, the program enters an infinite loop;
• If HaltChecker says the program loops forever, the program stops immediately.

When this program analyzes itself, both outcomes become impossible. If HaltChecker predicts that it halts, the program loops forever. If it predicts an infinite loop, the program stops. This contradiction shows that no algorithm can correctly determine halting for every possible program. The result introduced the concept of undecidable problems and demonstrated that there are fundamental limits to what computers can compute.

The Traveling Salesman Problem (TSP) is one of the most famous optimization problems in computer science. The problem is simple: a salesman must visit each city exactly once and return to the starting point while taking the shortest possible route. As the number of cities increases, the number of possible routes grows extremely fast.

Because of this rapid growth, finding the exact optimal route becomes very difficult for large datasets. Despite its simplicity, TSP has many practical applications, including logistics planning, airline scheduling, circuit board design, and DNA sequencing. It is considered an NP-hard problem, meaning no efficient algorithm is known for solving large instances perfectly.

The Graph Isomorphism Problem asks whether two graphs are structurally identical. A graph is a set of nodes connected by edges. Two graphs are isomorphic if one can be transformed into the other simply by renaming the nodes while preserving the connections between them. Although the idea sounds straightforward, determining whether two large graphs share the same structure can be surprisingly difficult.

This problem appears in areas such as chemical compound analysis, pattern recognition, computer vision and network analysis. For many years its computational complexity was unclear because it was not known to be either efficiently solvable (in P) or NP-complete. In 2015, computer scientist László Babai proposed a quasi-polynomial time algorithm that significantly improved the best known solutions, but the exact classification of the problem remains an open question.

The Boolean Satisfiability Problem (SAT) is one of the most important problems in computer science. The question is simple: given a logical formula made of variables and logical operators, can we assign truth values to the variables so that the entire formula becomes true? For example, consider the formula:

# (A OR B) AND (NOT A OR C)

Is there a combination of true and false values for A, B, and C that makes the formula true?

In 1971, computer scientist Stephen Cook proved that SAT is NP-complete, meaning it belongs to a class of problems that are believed to be extremely difficult to solve efficiently. If SAT could be solved in polynomial time, many other NP problems could also be solved efficiently.

Despite this theoretical difficulty, modern SAT solvers have become extremely powerful and are widely used in practice, including hardware verification, software testing, automated theorem proving, and planning and scheduling. SAT demonstrates a fascinating paradox in computer science: a problem can be theoretically hard, yet still practically useful thanks to clever algorithms and heuristics.

The Busy Beaver Problem explores the limits of what computers can compute. It asks: for a Turing machine with a fixed number of states, what is the maximum number of steps it can execute before halting? The machine that achieves this maximum is called the Busy Beaver.

Although the definition is simple, the Busy Beaver function grows faster than any computable function. Determining its value requires knowing whether many machines eventually halt, which makes the problem closely related to the Halting Problem. Because of this, exact values are known only for very small machines.

The Busy Beaver function is one of the clearest demonstrations of the fundamental limits of computability.

The Collatz Conjecture is one of the simplest unsolved problems in mathematics with a strong connection to computation. The rule is simple: start with any positive integer. If the number is even, divide it by 2. If it is odd, multiply it by 3 and add 1. Repeat the process. The conjecture states that every starting number will eventually reach 1. For example:

6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Despite its simplicity, no one has proven that this always happens. Computers have tested extremely large ranges of numbers and the sequence always reaches 1, but a general mathematical proof is still unknown.

Computer science is not only about building faster computers or writing better software. At its core, it is about understanding the nature of computation itself.

Problems like P vs NP, the Halting Problem, and the Busy Beaver Problem reveal that there are deep limits to what computers can do. Other problems, like the Traveling Salesman Problem and SAT, show how simple questions can lead to enormous computational complexity.

Despite decades of research, many of these questions remain unanswered. Solving even one of them could fundamentally change fields such as cryptography, optimization, artificial intelligence, and mathematics.

In many ways, these problems represent the frontier of computer science, reminding us that even in a field built on logic and algorithms, there are still mysteries waiting to be solved.

Q: What is the most important unsolved problem in computer science?

A: The P vs NP problem is widely considered the most important open problem in computer science. It asks whether problems that can be verified quickly can also be solved quickly. A solution would have major implications for cryptography, optimization, and algorithm design.

Q: Why are unsolved problems in computer science important?

A: These problems define the limits of computation and influence many real-world technologies. Understanding them helps researchers design better algorithms, improve security systems, and understand what computers can and cannot do.

Q: What is an NP-complete problem?

A: An NP-complete problem is a problem that is at least as difficult as the hardest problems in NP. If one NP-complete problem can be solved efficiently, then all problems in NP could also be solved efficiently.

Q: Is the Traveling Salesman Problem solved?

A: The problem can be solved exactly for small datasets, but for large numbers of cities it becomes computationally difficult. Researchers often use approximation algorithms that produce near-optimal solutions.

Q: Why is the Halting Problem impossible to solve? A: Alan Turing proved that no algorithm can determine for every possible program whether it will eventually stop running or continue forever. This result established that some computational problems are fundamentally undecidable.

Q: Could quantum computers solve these problems?

A: Quantum computers may solve some problems faster than classical computers, but they do not eliminate the fundamental limits of computation. Problems like the Halting Problem would remain unsolvable even with quantum computing.