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

• Временная и пространственная сложность алгоритмов/Задачи/Машина Тьюринга. Количество.
  ... 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
• Вероятность/Задачи/Curse-of-dimensionality
  ... сфере плотностью бросают $N$~точек.
  Найти медиану расстояния от центра сферы до ближайшей точки.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  505 байт (4 слова) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/Разрешимость конкатенации
  ... . Является ли разрешимой их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\}$
  \newline\newline
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  344 байт (16 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/a^b eq c mod d in P
  ... mod\, d\,\}\, \text{принадлежит}\,P
  2. Укажите два слова, принадлежащие языку, и два слова, не принадлежащие языку.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  453 байт (16 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Язык планарных графов
  ... или матрицей смежности)}.
  Покажите, что L_{planar} ∈co−NP .
  Подсказка: посмотри Th. Понтрягина — Куратовского
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  499 байт (11 слов) - 06:50, 4 мая 2023
• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Гамильтонов граф
  ... определить, что граф гамильтонов, но и найти в нем какой-нибудь гамильтонов цикл (если он существует).
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  463 байт (2 слова) - 06:50, 4 мая 2023
• Временная и пространственная сложность алгоритмов/Задачи/замки и ключи
  ... . Удивительным кажется то, что для этой задачи построен
  детерминированный o( $n^2$ )-алгоритм. Он очень хитрый.
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  1 КБ (9 слов) - 06:50, 4 мая 2023
• Формально об алгоритмах. Вычислительные модели/Задачи/Конкатенция P
  ... >
  Пусть $L_1,L_2 \in P$. Принадлежит ли $P$ их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\} \in P$?
  </latex>
  [[Категория:Решенные задачи]]
  [[Категория:Теоретические задачи]]
  290 байт (18 слов) - 06:50, 4 мая 2023

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