P, NP, PSPACE and BQP
A brief summary of this alphabet soup of computational complexity.
P — Problems that can be SOLVED in polynomial time.
NP — Problems that can be VERIFIED in polynomial time.
NP complete — The most difficult problems in the NP class.
PSPACE — Problems that require a polynomial amount of memory.
BQP — Problems can be solved efficiently on a quantum computer.
A more elaborate explanation.
P — These are “easy” problems to be solved.
NP — These are “easy” problems to be verified. That is, given an answer, it is easy to check whether or not it meets the problem. However, reaching the solution is not necessarily easy.
Therefore, there may be problems that are easy to verify but difficult to solve.
Simple example. Rearrange the following word:
imblasnnugcr
It is much more difficult to find the solution than to see that “unscrambling” is the answer.
The most difficult problems of all NP are called NP-Complete. Several real-life problems, such as Satisfiability, are NP-Complete.
There is also the NP-Hard, which are problems at least as difficult as the NP-complete. Optimization problems are like that. NP-Complete is to find a solution, NP-Hard, to find the best solution. The famous Traveler Salesman problem is an example of an optimization problem.
A major unsolved problem in the world is whether P = NP. Until today, it has not been possible to prove that they are the same or not different. It is, indeed, one of the challenges of the Millennium from Clay Institute, worth 1 million dollars!
BQP are problems that can be solved by a quantum computer. It is suspected that it is possible to solve problems that are more difficult than class P, but without solving the NP-complete.
Therefore, the figure representing the degrees of complexity is just an idea. If P is equal to NP, we wouldn’t even need a quantum computer! It would be enough to use this algorithm, which solves difficult problems easily.
The P vs NP problem is complicated to prove, until today it has not been solved.
However, to this day difficult problems remain difficult, which is a strong indication that P is different from NP, and that difficult problems will remain difficult — and that quantum computers will be very useful.
https://en.wikipedia.org/wiki/BQP
https://en.wikipedia.org/wiki/P_versus_NP_problem
Technical ideas with a bit of philosophy
Join the Quantum Computing study group:
