Open Classic Hard Problems

Ссылки сюда (7) →

Всего страниц найдено: 5.

---

Задача «Minimum Register Sufficiency»^©

---

Беру задачу «Hardprob/Minimum Register Sufficiency» себе!

• Направленный ациклический граф G=(V,A)
• Найти вычисление на G, которое использует k регистров, т.е.
  • порядок v₁, …, v_n на вершинах V
  • последовательность S₀, …, S_n подмножеств V, удовлетворяющих
    • S₀ — пустое
    • S_n — содержит все вершины с нулевой входящей степенью в G
    • 1 ≤ i ≤ n, , , и содержит все вершины u, для которых
• Минимизировать число регистров,т.е. k.

---

Задача в лаб17 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «PO1»

---

---

---

Задача «Minimum Permutation Group Base»^©

---

Беру задачу «Hardprob/Minimum Permutation Group Base» себе!

• Группа G перестановок из n символов.
• Найти базу для G, т.е. последовательность точек b₁, …, b_k, такой, что единственный элемент в G фиксирующий все эти b_i это идентичное преобразование.
• Минимизировать размер базы, т.е. k.

---

Задача в лаб17 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Minimum Locally Testable Automaton Order»^©

---

Беру задачу «Hardprob/Minimum Locally Testable Automaton Order» себе!

• Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j, такое что входит или нет строка x в этот язык зависит от …
  • префикса и суффикса x длины j-1,
  • набора подстрок x длины j.
• Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
• Минимизировать значение порядка, т.е. j.

---

Задача в лаб17 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Shortest Computation»^©

---

Беру задачу «Hardprob/Shortest Computation» себе!

• Недетерминированная машина Тьюринга M, двоичная входная строка x.
• Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
• Минимизировать длину кратчайшей из этих строк,т.е. .

---

Задача в лаб17 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Longest Computation»^©

---

Беру задачу «Hardprob/Longest Computation» себе!

• Недетерминированная машина Тьюринга M, двоичная входная строка x.
• Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
• Максимизировать длину кратчайшей из этих строк,т.е. .

---

Задача в лаб17 (рид-онли просмотр)

---

• Задача в базе NP-полных задач Вигго Кана

---

---

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.