Вариант 3797922940.
Что верно для NP-полных и NP-трудных задач:
Является ли конкатенация двух разрешимых языков перечислимой?
Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.
Что будет верно?
Существует ли биекция между классами и ?
Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.
Что верно?
Является ли пустое множество разрешимым?
Рассмотрим две задачи разрешения, P1 и P2, такие что
Что можно утверждать?