We Need to Talk About NP-things
Let's take a little detour from our series on Quantum Computing and get a solid understanding of Computational Complexity
Hello, Hypers!
Computational Complexity is one of those infinite topics that we can talk about every day and still find new interesting and unknown facts. It is a difficult topic in Computer Science but, if explained well, it can also be very funny. In this new issue of Under the Hype, I’ll be trying to entertain you with some Computational Complexity knowledge.
I know I was talking about Quantum Computing but believe me, with these bits of information we’ll understand better what the quantum world has to say in the computing field. So, let’s get started!
Disclaimer: You’ll enjoy more this article if you know what a Turing Machine is. If not, don’t worry and read on, but don’t forget to let me know if you want me to explain it in a future post ;-)
Computational Theory vs. Computational Complexity
The very foundation of Computer Science is Computational Theory. This is the field that studies which problems can be solved with an algorithm and which ones can not. To determine the computability of problems (whether the problem is solvable by an algorithm or not), we need a computational model. These models are a definition of what an algorithm is.
The most famous computational model is the Turing Machine. Alan Turing came up with a theory of states, tapes, and transitions that are the theoretical definition of an algorithm. But this is not the only computational model out there, there are many of them like the Lambda Calculus of Alonzo Church.
It turns out that all these computational models are equivalent. That is, if we can solve a problem with one of them, then we can solve the problem with any other of them.
It is important to note that in Computational Theory we are just interested in whether the problem can be solved or not. We don’t care about how long does it take to solve it in practice. But, of course, a problem that would take thousands of years to solve is unsolvable in practice. So, Computer Science also tries to discover what are the problems that are feasible in a practical sense. Computational Complexity studies, among other things, feasible and unfeasible problems.
P vs. NP again!
If you know a little bit about Computer Science, you have surely heard about NP and P problem classes. Unfortunately, these concepts are frequently misunderstood, so I want to make sure here in Under the Hype everybody gets them right.
The NP class defines the problems that are easily verifiable. By verifiable we mean the process of checking if a proposed solution is really a solution to the problem. By easily we mean that this verification can be done in polynomial time. That is, the function of the time that takes the verification with respect to the input of the problem is polynomial.
Note: Here we’ll use the word time but we are not talking of time precisely. But let’s talk about this in a future post.
For example, imagine the problem of factorizing a number in its prime factors. A solution to this problem is a list of prime numbers that when multiplied together yield the input number.
Non-deterministic Polynomial Problems. Painting. app.leonardo.ai
It is easy to check that a proposed solution actually solves the problem. We just need to check that every number in the output list is a prime number and then check that the multiplication of all of them yields the original number. Easy right?
Just to summarize, we say that an NP problem is an easily verifiable problem. Then, what is a P problem?
A problem in the P class is a problem that is easily solvable. That means that we can find a solution in polynomial time. But in this case, the algorithm that finds the solution is itself a verification of that solution so P is a subset of NP. Take note of this because that’s one of the most misunderstood facts on this topic.
What we don’t know yet is whether there are problems in NP that are not in P. This is one of the hardest problems in the history of science. There are NP problems that we haven’t been able to prove or disprove they are in P. These are very special problems in the sense that they are easily verifiable but hard to solve.
For example, cryptography heavily relies on these problems. To decode a message without having the proper key, you need to solve an unfeasible problem, but it is easy to prove that you own the required key.
Missed our intro to cryptography. I got you:
The computational model jumps in
We talked about computational models and the Turing Machine. Then we talked about easy and hard problems. One question that can arise is: Is there a computational model that can solve hard problems faster?
According to the Church-Turing Thesis, there is no computational model that allows us for solving more problems than the ones we solve with the classical Turing Machine. But this still leaves the door open to make feasible the problems that are unfeasible with the classical Turing Machine.
For example, we can think of a non-deterministic Turing Machine. This machine can be in different states at the same time. Problems in NP (Non-deterministic Polynomial) can be solved in polynomial time with this type of model.
A non-deterministic Turing Machine. Should remind Van Gogh style. Don't use too many colors. app.leonardo.ai
Another example is the Probabilistic Turing Machine, which is also non-deterministic but in a special way. This machine jumps from one state to another with a certain probability. It is also known that these probabilistic machines can solve hard problems faster with high confidence. We need to add this “high confidence” disclaimer because the result of the computation can vary due to the probabilistic nature of the machine.
Quantum Computers (Aha! It’s a trap!) are not Non-deterministic Turing Machines or Probabilistic Turing Machines but they have a lot of points in common with both models. They have probabilistic and non-deterministic components, and also they can solve classical unfeasible problems faster.
For example, the problem of factorizing a number does not have a polynomial solution in a classical Turing Machine (yet). Still, we can solve it faster in a Quantum Computer with Shor’s Algorithm. Curiously, this is one of the problems that is key for cryptography.
Conclusion
The process of analyzing the feasibility and complexity of problems should take into account not just the problem but the computational model too. If we trust in the Church-Turing Thesis, then we accept that a new computational model won’t solve an uncomputable problem, but that doesn’t mean it can’t solve an unfeasible problem in a reasonable amount of time.
Quantum Computers have features that make them different from classical Turing Machines and they can solve unfeasible problems like prime factorization in polynomial time. Then, what are the questions that arise from this?
Exactly what kind of unfeasible problems are feasible with Quantum Computers?
What does a Quantum Algorithm look like?
How similar is a Quantum Computer to a Non-Deterministic or Probabilistic Turing Machine?
Those are some of the big questions we’ll try to answer in this series. So stay tuned and don’t forget to subscribe.
See you next week!
Very good! I noticed you didn't mention NP-Completeness, I assume on purpose...