Polünoomülesanne

Polünoomülesanne is the Estonian term for the polynomial problem. This generally refers to problems that can be solved by algorithms whose time complexity is bounded by a polynomial function of the input size. In computer science, these problems are considered computationally tractable, as opposed to exponential time problems which become intractable very quickly as the input size grows.

The class of problems that can be solved in polynomial time by a deterministic Turing machine is denoted as P. The class of problems that can be solved in polynomial time by a non-deterministic Turing machine is denoted as NP. A central question in theoretical computer science is whether P = NP, meaning if every problem whose solution can be quickly verified also has a solution that can be quickly found.

Many important problems in areas such as optimization, cryptography, and artificial intelligence are polynomial problems. For example, sorting a list of numbers, finding the shortest path in a graph, and multiplying matrices are all polynomial time problems. These algorithms are crucial for the efficient operation of modern computing systems and many scientific endeavors.

Conversely, problems that cannot be solved within polynomial time are often referred to as intractable or computationally hard. Examples include the traveling salesman problem in its general form and factoring large integers, which are foundational to the security of many cryptographic systems. The distinction between polynomial and non-polynomial time complexity is fundamental to understanding the limits of computation.