Introduction to the
When we do combinatorial optimization, we need to solve various problems, which can be divided into P, NP, NPC problems and so on according to the complexity of the problem. Today I’m going to introduce you to these types of questions.
P problem
In computational complexity theory, P (also known as PTIME or DTIME) is the basic complexity type. It refers to all decision problems that can be solved in polynomial time using a deterministic Turing machine.
Here we give the definition of P, if a formula language L is a P type, then this is true if and only if there is such a deterministic Turing machine M:
- For all inputs, M runs in polynomial time
- For all x’s in L, the output of M is 1
- For all x’s not in L, the M output is 0
Common P problems include decision versions of linear programming, calculating the greatest common factor and finding the greatest match. In 2002, it was shown that the problem of determining whether a number is prime is also a P problem.
NP problem
In the computational complexity theory, NP (Nondeterministic polynomial time) polynomial time is mainly used to measure the complexity of classification decision problems. NP is a set of decision problems for which an answer of “yes” indicates that the instance can be verified in polynomial time using a deterministic Turing machine.
NP is actually made up of two phases, the first consisting of a guess about the solution, which is generated in a nondeterministic manner, and the second consisting of deterministic algorithms, which verify whether the guess can solve the problem. So NP= nondeterministic + polynomial.
According to the definition of P and NP, we can find that all P problems are NP problems, because the definition of P is that all problems can be solved definitively in polynomial time, and the definition of NP is that the problem can be verified in polynomial time.
But NP contains more problems, and the hardest problems in NP are called NP-complete problems. Algorithms that solve such problems in polynomial time can also solve any other NP problem in polynomial time.
Examples of NP problems
In computer science, many search optimization problems can be considered NP problems. The traveling salesman problem is a typical NP problem.
“Given a list of cities and the distance between each pair of cities, find a shortest path to visit each city once and then return to the original city.” This is an NP problem in combinatorial optimization, important in theoretical computer science and operational research.
Some NP problems are hard to solve
Because NP problems contain many very important problems in practical life, people have made great efforts to find polynomial time algorithms in NP. However, there are still many problems in NP that seem impossible to solve in polynomial time. Whether these problems can be solved in polynomial time is one of the biggest unsolved problems in computer science.
An important concept introduced in this context is the nP-complete decision problem set, which is a subset of NP and can be informally described as the “hardest” problem in NP. If we say that a problem turns out to be an NPC problem, it means that no polynomial time algorithm can be found on the problem.
However, in practical applications, it is usually not necessary to spend a lot of computation to find an optimal solution, but it is possible to find a suboptimal solution in polynomial time, which is sufficient for practical applications.
NPC problem
In computational complexity theory, NPC problems are those that satisfy:
- An uncertain Turing machine can be solved in polynomial time.
- A deterministic Turing machine can solve in large time complexity (EXPTIME or brute force search algorithm) and verify its solution in polynomial time.
- It can be used to simulate any other problem with similar solvability (all other problems in NP can be converted or reduced to this problem in polynomial time).
According to Rule 3, since NPC problems are a more complex form of NP problems, if you can find a polynomial algorithm that solves an NP-complete problem, then all NP problems will be easily solved.
For example, a quadratic equation with one variable can be reduced to a quadratic equation with one variable by changing the quadratic coefficient to 0. Through continuous specification, we can get a more complex but more widely applied algorithm to replace the less complex but less widely applied algorithm of a class of problems.
Although it is possible to verify a solution to an NPC problem “quickly”, there is no known way to find a solution quickly. That is, as the size of the problem increases, the time required to solve it using any currently known algorithm increases rapidly.
No method has yet been discovered for computing solutions to NP-complete problems, but computer scientists and programmers still encounter NP-complete problems frequently. Np-complete problems are usually solved by using heuristics and approximation algorithms.
NP-hard
In computational complexity theory, NP-hard is a description of a class of problems that are “at least as hard as the hardest problems in NP”. A simple example of an NP-hard problem is the subset sum problem.
If a known NPC problem can be reduced to this problem, then the problem is called nP-hard.
So NPC problems must be NP-hard problems, but not all NP-hard problems are NPC problems.
P and NP problems
P and NP problems are the main unsolved problems in computer science. It talks about whether a problem can be solved quickly if it can be verified quickly.
P means that a solution to the problem can be found in polynomial time, while NP means that a candidate answer can be quickly verified if found.
Under normal circumstances, everyone works. = NP, which means you can’t solve it in polynomial time, but you can verify it in polynomial time.
According to whether P and NP are the same, we make the relation diagrams of P, NP, NPC and NP-hard respectively.
This article is available at www.flydean.com/04-p-np-npc…
The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!
Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!