воскресенье, 7 февраля 2021 г.
Cook's problem
Cook's problem (formulated in 1971)
Field: mathematical logic and cybernetics
It is also called "Equality of classes P and NP", and it is one of the most important problems in the theory of algorithms, logic and computer science.
Can the process of verifying the correctness of the solution of a problem last longer than the time spent on the solution of this problem itself (regardless of the verification algorithm)?
Sometimes it takes a different amount of time to solve the same problem, if you change the conditions and algorithms. For example: in a large company, you are looking for a friend. If you know that he is sitting in a corner or at a table , then it will take you a split second to see him. But if you don't know exactly where the object is, you will spend more time searching for it, bypassing all the guests.
The main question is: all or not all tasks that can be easily and quickly checked, can also be easily and quickly solved?
What is the solution? This is both a question and an answer.
What is the answer? This is the result of mathematical actions or an epiphany - on a whim, they answer the question.
Checking the correctness of the solution? Proof of compliance of the answer to the question.
What is a quickly and easily check, it is easy and fast to solve? This is inexplicable. Everyone understands the term (easily) in their own way.
So the main question is, can all or not all the tasks that can be checked be solved?
Checking the correctness of the solution of a problem, can it take longer than the time spent on the solution of this problem itself? Yes, it can. The answer to the question and the answer about the correctness of the answer to the question are two different tasks. And they will naturally require different time intervals to solve. In addition to the answer by inspiration on a hunch, because in this case, the answer to the question obtained as a result of mathematical actions did not exist at all.
The time for solving problems with answers on insight on a hunch is not defined. Such tasks may not be solved at all in real time for one person.
The equality of the classes P and NP is not true in this case.
Подписаться на:
Комментарии к сообщению (Atom)
Комментариев нет:
Отправить комментарий