NP-промежуточный

От / / Оставьте комментарий

NP-промежуточное звено Задачи, относящиеся к классу сложности NP, но не относящиеся ни к классу P, ни к NP-полному, называются NP-промежуточными.  […]

Complexity classes, Классы сложности

NP-промежуточное звено

  • Задачи, относящиеся к классу сложности NP, но не относящиеся ни к классу P, ни к NP-полному, называются NP-промежуточными. 
  • Теорема Ладнера утверждает, что если P ∈ NP, то NPI не является пустым. 
  • Если проблемы с NPI существуют, то P ∈ NP, что означает, что P = NP только если NPI пуст. 
  • Некоторые «естественные» задачи могут иметь свойство NP-промежуточности, как теорема о дихотомии Шефера. 
  • Список проблем, которые могут быть NP-промежуточными, включает алгебру и теорию чисел, логическую логику, вычислительную геометрию и топологию, теорию игр и графовые алгоритмы. 

Полный текст статьи:

NP-промежуточный — Википедия

Похожие статьи:

  1. Пункт «Полярность» Элемент полярности Отрицательная полярность (NPI) в английском языке включает в себя элементы, которые имеют противоположное значение...
  2. Логика в исламской философии Логика в исламской философии Раннее исламское право и логика Исламские философы внесли значительный вклад в развитие...
  3. NP-твердость NP-твердость Определение NP-сложности NP-сложная задача — это задача, для которой существует полиномиальное сокращение от любой задачи...
  4. Четырехзначная логика Четырехзначная логика Основы четырехзначной логики Четырехзначная логика включает четыре истинностных значения: true, false, оба и ни...
  5. СЛЕДУЮЩИЙ ВРЕМЯ СЛЕДУЮЩИЙ РАЗ Определение NEXPTIME NEXPTIME — это класс задач, которые могут быть решены за полиномиальное время...
  6. Теорема об иерархии времени Теорема о временной иерархии Теоремы о временной иерархии Теоремы о временной иерархии описывают иерархию классов сложности,...
  7. Концептуальное письмо Бегрифшрифт Обзор Begriffsschrift Begriffsschrift — это логическая система, разработанная Готлобом Фреге в 1879 году.  Фреге стремился...
  8. ♯П ♯П Определение класса сложности #P #P — это набор задач подсчета, связанных с задачами решения в...
  9. Дерево проблем Дерево проблем Деревья проблем используются для решения проблем и выявления первопричин и потенциальных решений.  Существуют два...
  10. Список проблем с рюкзаком Список проблем с рюкзаком Определение и задачи Рюкзак — это проблема выбора предметов с учетом их...
  11. RE (сложность) RE (сложность) Определение и свойства класса RE Класс RE включает задачи, которые могут быть решены машиной...
  12. ТФНП ТФНП Определение и классификация задач TFNP — это класс задач, которые не могут быть решены за...
  13. L (сложность) L (сложность) Определение и характеристики класса L L — класс задач, решаемых детерминированной машиной Тьюринга с...
  14. PSPACE ПРОСТРАНСТВО Определение PSPACE PSPACE — это класс задач, решаемых машиной Тьюринга за полиномиальное время с использованием...

Оставьте комментарий

Прокрутить вверх