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

• Полиномиальная иерархия/Задачи/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
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/HALT-and-NP
  ... на x за конечное число шагов.
  Является ли HALT:
  * NP-полным
  * NP-трудным
  * PSPACE-полным
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  383 байт (10 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3SAT-TAUTOLOGY-reducibility
  ... [[3SAT]] и [[TAUTOLOGY]] полиномиально сводятся к друг другу по Карпу, то
  [[NP]] = [[CoNP]].
  <!-- P1401 -->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  301 байт (7 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Unary-lang-and-NP
  ... нулей.
  Покажите, что если существует один из таких языков <m>L_{0}</m>, что <m>L_{0} \in NPC</m>,
  то <m>P=NP</m>.
  [[Категория:Решенные задачи]]
  [[Категория:P1401]]
  [[Категория:Теоретические задачи]]
  456 байт (14 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/E13SAT-NPC
  ... из таких 3КНФ, которые
  * выполнимы
  * и в этом выполняющем наборе, в каждой скобке ровно один истинный литерал.
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  429 байт (2 слова) - 06:56, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/Возведение в степень за логарифмическое время
  ... -программу, которая по входу (a,b), где a,b > 1, вычисляет a^b. Время работы программы должно быть ''О''(log ''b'')
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  516 байт (15 слов) - 06:50, 4 мая 2023

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