Математическая логика и теория алгоритмов

1) является алгоритмически неразрешимой; 2) не является Л'Р-полной задачей; 3) является 7/Р-полной задачей; 4) является задачей, не принадлежащей классу NP-, 5) является задачей, не имеющей решения. 10. Укажите, какое из следующих утверлсдений ложно: 1) задача является NP полной, если она входит s NP к каждая задача из NP полиномиально сводится к ней; 2) NP класс задач содери<ит задачи которые можно решить неде­ терминированными алгоритмами, работающими в течение полиномиального времени; 3) задача является NP трудной, если каждая задача из NP полиномиально сводится к ней; 4) если одновременно задача Zi полиномиально сводится к задаче Z2 и Z2 полиномиально сводится к задаче Zj, то задачи Zi и Z2 полиномиально эквивалентны; 5) задача имеет экспоненциальную временную сложность, если хотя бы один из алгоритмов ее решения имеет экспоненциаль­ ную временную сложность. Ответы к тестам самоконтроля Номер теста Номер вопроса теста 1 2 3 4 5 6 7 8 9 10 Номер ответа на данный вопрос теста I 4 2 I 4 2 4 2 5 3 3 2 5 2 4 5 1 2 2 3 5 4 3 1 5 3 2 4 2 5 3 4 2 4 5 1 2 4 3 2 4 4 1 5 5 2 5 2 4 i 3 5 1 2 5 6 2 4 3 5 4 3 4 2 3 5