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

• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-hamilton-cycle-in-np
  ... графов (т.,е. графов, не содержащих ни одного гамильтонова цикла)
  принадлежит coNP.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  608 байт (5 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-limited-3sat-npc
  ... трех раз, причем каждый литерал - не больше двух.
  Покажите, что и эта задача NP-полна.
  [[Category:Решенные задачи]]
  <!--Вообще-то, решения уже есть-->
  [[Категория:Теоретические задачи]]
  590 байт (8 слов) - 06:50, 4 мая 2023
• PCP и аппроксимируемость/Задачи/ex-max2sat-in-npc
  ... выполнить
  больше чем <tt>K</tt>, количество скобок.
  Покажите, что эта задача NP-полна.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  557 байт (12 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-p-in-np-and-conp
  Покажите, что <m>P \subseteq NP \cap coNP</m>.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  233 байт (10 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-polynomial-diofant-is-in-np
  ... NP$, т.к.
  если оракул-Мерлин предоставит решение $v$,
  доказывающее принадлежность полинома $p \in DFNT$, ... 0$.
  Прав ли студент?
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  686 байт (14 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-triange-in-p
  ... полиномиальный алгоритм для проверки, есть ли в заданном графе хотя бы один «треугольник».
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  363 байт (3 слова) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/nonapprox TSP
  ... с мультипликативной ошибкой не превышающей величины, зависящей только от числа вершин графа.
  [[Category:Решенные задачи]]
  <!--Вообще-то, решения уже есть-->
  [[Категория:Теоретические задачи]]
  539 байт (9 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/НМТ для Subset Sum
  {{:Subset Sum}}
  Постройте недетерминированный полиномиальный алгоритм для задачи [[Subset Sum]]
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  331 байт (7 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Раскраска графа в два цвета
  ... графа в два цвета ==
  Постройте полиномиальный алгоритм для раскраски графа в два цвета.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  411 байт (3 слова) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-average-expect-max-nk
  ...
  <latex>
  \mathrm{E} \max_k|N_kN_k| \leq \sum_{k=1}^m {\binom{m}{k}} \mathrm{P}(k).
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  372 байт (21 слово) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-bad-data
  Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  341 байт (4 слова) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-good-data
  На каких входных данных алгоритм из этой темы, будет работать <m>O(m)</m>?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  302 байт (7 слов) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для задачи о рюкзаке/Задачи/Проблемы определения «в среднем»
  ... распределение: Вероятность появления каждой входной строки.
  ;<m>x_n</m>: вход длины n.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  680 байт (35 слов) - 06:50, 4 мая 2023
• Полиномиальный в среднем алгоритм для задачи упаковки/Задачи/ex-packing-average-bad-and-good-data
  ... для упаковки
  заставят его работать экспоненциально долго?
  * А какие — за <m>O(n^3)</m>?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  451 байт (7 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-halt-empty-tape
  ... слове», т.е. для данной МТ <tt>T</tt> определить,
  остановится ли она на пустом слове.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  453 байт (7 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-lost
  ... 4815162342» встречается в десятичном разложении числа
  $\pi$ не менее чем $n$ раз подряд.
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  463 байт (11 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-no-enumeration-of-cycled
  ... за
  другой все машины Тьюринга, которые не останавливаются, будучи
  запущенными на пустой ленте.
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  465 байт (3 слова) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-obfuscation-undecidable
  ... : попадет ли машина в это
  состояние хотя бы для одного входного слова <tt>x</tt>?
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  581 байт (14 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/ex-turing-copy-lowerbound
  ... можно сказать про $T'(n)$,
  которое есть минимальное время ее работы на входах длины $n$?
  </latex>
  <!--Вообще-то, решения уже есть-->
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  815 байт (21 слово) - 06:50, 4 мая 2023

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