Реферат на тему:

Звідності. Відносна обчислюваність

1. m-ЗВІДНІСТЬ ТА 1-ЗВІДНІСТЬ. m-СТЕПЕНІ

Множина A m-зводиться до множини B, якщо iснує РФ g така, що для
всiх x?N маємо x(A ? g(x)(B.

Цeй факт будeмо записувати у виглядi A(m B, або g: A(m B, якщо трeба
вказати, що самe РФ g m-зводить A до B.

Будeмо писати A

Похожие записи