D
D
Denis Karakchiev2015-06-04 02:37:26
Programming
Denis Karakchiev, 2015-06-04 02:37:26

What is the essence of polynomial transformations?

Perhaps the last 2 tags are superfluous, I just didn’t quite orient myself. Problems of P and NP classes are related to the theory of algorithms. But when trying to find something about polynomial transformations, I only see related to geography.
The bottom line: I'm preparing to enter the master's program (passing the exam) in the direction of "Mathematics and Computer Science". This is due to the fact that geography does not fit well here. Thanks in advance for your replies.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
D
Dvvarreyn, 2015-06-08
@Satori_Kanzo

polynomial transformations
This is similar to translating from Russian into English and vice versa.
Polynomial reducibility, less often transformability, Karp reducibility, sometimes just reducibility.
In English, polynomial-time reduction, very rarely transformation.
Briefly, the point is that two problems are polynomially reducible if there is a polynomial transformation from one to the other. In the class P (NP) there are problems to which all other problems from the class are reduced.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question