Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 3287358363.

Ваше имя*:

Вопрос 1

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1
  2.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0
  3.  , то T останавливается и выводит 1, а если , то T зацикливается
  4.  , то T останавливается и выводит 0

Вопрос 2

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

  1.  Q — NP-трудная
  2.  R — NP-полная
  3.  R — NP-трудная
  4.  Q — NP-полная

Вопрос 3

Пусть

  • — задача поиска гамильтонового цикла в графе , где V — делится на 3.
  • — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

  1.  Они обе не NP-hard.
  2.  Все остальные варианты — неверны.
  3.   и — NP-трудны.
  4.   — NP-hard, но не .
  5.   — NP-hard, но не .

Вопрос 4

Пусть сводится по Карпу к . Выберите верное утверждение:

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 5

Для какой задачи не существует (при условии ) полиномиального алгоритма:

  1.  Аппроксимация Рюкзака (Knapsack) с точностью 0.9
  2.  Поиск эйлерова цикла в графе
  3.  Аппроксимация MAX-SAT с точностью 0.9
  4.  Аппроксимация Рюкзака (Knapsack) с точностью 0.017
  5.  Кратчайшие пути в графе

Вопрос 6

Является ли разрешимым множество натуральных чисел, не превосходящих :

  1.  Нет
  2.  Да
  3.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;

Вопрос 7

  1.  BPP
  2.  PSPACE
  3.  RP
  4.  ZPP
  5.  coRP
  6.  NP
  7.  PP
  8.  coZPP

Вопрос 8

Задачи 3SAT и 2SAT:

  1.  Обе NP-полны
  2.  Первая неразрешима и вторая — NP-полна.
  3.  Первая NP-полна и вторая в P.
  4.  Обе в P
  5.  Все остальные варианты — неверны.

Вопрос 9

Существует ли биекция между классами и ?

  1.  Нет, не существует;
  2.  Да, существует;
  3.  Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;

Вопрос 10

Найдите неверное утверждение:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»