On a Saturday night, you attended a grand party. It's embarrassing. You want to know if there is anyone you already know in this hall. The host of the party hinted to you that you must know Ms. Ross sitting in the corner near the dessert plate. You don't need a second to glance over there and find that the host of the party is right.

However, if there is no such hint, you must look around the whole hall and look at everyone one by one to see if there is anyone you know.

Generating a solution to a problem usually takes more time than verifying a given solution. This is an example of this common phenomenon. Similarly, if someone tells you that the number 137 1742 1 can be written as the product of two smaller numbers, you may not know whether to believe him, but if he tells you that this number can be decomposed into 3607 times 3803, then you can easily verify that this is correct with a pocket calculator.

It is found that all complete polynomial uncertainty problems can be transformed into a kind of logical operation problems called satisfaction problems. Because all possible answers to such questions can be calculated in polynomial time, people want to know whether there is a deterministic algorithm for such questions, and they can directly calculate or search for the correct answers in polynomial time. This is the famous NP=P? Guess.

Whether we write a program skillfully or not, it is regarded as one of the most prominent problems in logic and computer science to determine whether an answer can be quickly verified with internal knowledge, or it takes a lot of time to solve it without such hints. It was stated by Steven Kirk in 197 1.