Результаты поиска

• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/Плохой пример
  Придумайте пример, входной метрический граф, на котором алгоритм Кристофидеса дает наихудшую точность, т.е. 3/2.
  [[Category:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  310 байт (1 слово) - 06:50, 4 мая 2023
• Приближенный алгоритм для метрической задачи коммивояжера/Задачи/Четность вершин нечетной степени в MST
  <latex>
  Почему множество всех вершин нечетной степени в остовном дереве $T$ четно?
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  268 байт (3 слова) - 06:50, 4 мая 2023
• Уникальность минимального остовного дерева
  ... связный ненаправленный граф с ребрами попарно различной длины имеет только одно минимальное остовное дерево.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  362 байт (2 слова) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-exists-enumeration-of-halts
  ... выписывает одну за
  другой все машины Тьюринга, которые останавливаются, будучи
  запущенными на пустой ленте?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  374 байт (0 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/NP \cup co-NP \subseteq P^NP
  Докажите
  <m>
  NP \cup coNP \subseteq P^{NP}
  </m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  172 байт (8 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/P^SAT=P^NP
  Докажите <m>P^{SAT}=P^{NP}</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  155 байт (6 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/NP^SAT=\Sigma^p 2
  Докажите
  <m>NP^{SAT}=\Sigma^p_2</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  160 байт (6 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/compliment-in-ph
  ... любого натурального $k, \ k \geq 0$, верно соотношение
  $$
  L \in \Sigma^p_k \ \iff \ \{0,1\}^*\setminus L \in \Pi^p_k \ .
  $$
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  324 байт (17 слов) - 06:47, 18 декабря 2023
• Полиномиальная иерархия/Задачи/PH \subseteq PSPACE
  Докажите, что
  <m>PH\subseteq PSPACE</m>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  168 байт (5 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/PH collapse if PHC exists
  ... $ существует полный язык относительно полиномиальной сводимости по Карпу,
  то для некоторого $k$ $\Sigma^p_k=PH$.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  340 байт (8 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/P\poly contains unsolvable
  Показать, что <m>P/poly</m> содержит некоторые невычислимые функции.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  232 байт (4 слова) - 06:50, 4 мая 2023
• Вероятность/Задачи/Casino-n-k
  ... не выиграет определенную сумму <math>n \geq k</math>. Какова вероятность, что игрок проиграет все деньги?
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  670 байт (6 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/Теорема о неподвижной точке
  ... с номерами $n$ и $f(n)$ на одном и том же входе либо дают одинаковый ответ, либо оба зацикливаются.
  </latex>
  [[Category:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  536 байт (8 слов) - 06:50, 4 мая 2023
• Корректность алгоритма Прима
  Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  355 байт (0 слов) - 06:50, 4 мая 2023
• Полиномиальная иерархия/Задачи/NP!=co-NP
  Доказать, что NP ≠ coNP, если P ≠ NP
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  172 байт (4 слова) - 06:50, 4 мая 2023
• Жадные алгоритмы/Задача о покрытии отрезков точками
  ... каждому отрезку принадлежит хотя бы она точка. Предложить эффективный жадный алгоритм, оценить сложность.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  551 байт (3 слова) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/Машина Тьюринга. Количество.
  ... Sigma =\{a_0,...,a_n\}$, есть множество состояний $S=\{s_0,...,s_m\}$. Сколько существует машин Тьюринга для данных множеств?
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  365 байт (10 слов) - 06:50, 4 мая 2023

Просмотреть (предыдущие 20 | следующие 20) (20 | 50 | 100 | 250 | 500)