Solving any problem from the NP-complete class in the polynomial-time or rigorously proving it is impossible, will earn you $1 million.

There are many other NP-complete problems, and dozens are listed on Wikipedia.įinding the definite relation between P and NP classes of problems is considered one of the 7 most important open questions in mathematics. Given a map, can you color it using only three colors, such that no neighboring countries are of the same color? Given several boxes of various sizes, can you pack them into a given trunk? Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It was proven that finding an efficient solution to any of the challenges from the NP-complete subclass will make it possible to solve all the problems from the NP class. The hardest among NP problems are grouped in the NP-complete subclass. The time for solving problems from this class increases exponentially (exp(n), like interest on unpaid debt) with the problem size, but the solutions could be verified quickly, in polynomial time. Algorithms for these types of problems are not very efficient, and sometimes they are only somewhat better than trying every possible solution that exists. Such are, for example, the factorization of a big number into its prime factors, or for a given program and its input, answering will it run forever. The next complexity class is called NP, which stands for non-deterministic in polynomial time. Computers are efficient in solving these types of problems.Ĭomplexity classes of computational problems on classical computers Not easy to solve, but easy to check the solution - NP class The common thing for all these problems is that they all could be solved in time which increases only polynomially (for example, directly proportional to n, or growing quadratically, like n²) with the problem size. Easy problems for computers - P classĮasy problems for computers are multiplication, sorting, figuring out if there is a road from any town to every other city for a given map, etc. On the other hand, figuring out the winning strategy for the generalized Geography game (where players have to create a word that starts with the last letter of the previous word) is considered a very hard problem for a computer. The algorithms for solving the problems from different complexity classes are rated from horrible to excellent, based on the number of operations needed with the problem scaling.īack in the 1970s, it was understood that multiplication or alphabetizing a list of names will be easy problems for computers, as there are very efficient algorithms that can do so. Problems within the same class may look very different, but the common thing is that they all can be solved within the same time or memory budget. Nonetheless, once a functioning quantum computer is here, the question is: what kind of tasks it will be good at and what are its limits? Easy and hard problems for computersĪll types of problems the computer can answer can be classified into few groups based on their complexity when using the optimal algorithm. This challenge exists for all competing hardware technologies, and the solution is still not in sight. The practical limitation of building a quantum computer is decoherence, which is the unwanted interaction between the computer and its environment, and which introduces errors. It has its own challenges to become fully operational and commercially available, with the main ones being probably the quality of qubits and the error correction. This potential of quantum computers is that the concepts of quantum interactions are natural on quantum machines, while they probably cannot be efficiently simulated on classical ones.Ī quantum computer is, however, still not here.

However, quantum algorithms are attractive as they might be able to solve some problems faster than the classical ones, and in a few cases, even solve some problems faster than the classical computers can verify the answer. It is important to know that quantum algorithms won’t be able to solve any problems that classical algorithms cannot already solve. A quantum computer is a different type of machine that operates conceptually differently, utilizing the interference properties of quantum states, such as quantum entanglement and quantum superposition. The quantum computer isn’t just a next-generation computer with a faster processor and a bigger memory stick. Easy problems for classical and quantum computers

Microsoft big quantum error after all