Hardprob/Minimum Locally Testable Automaton Order

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

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

---

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

---

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

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

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

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