Долгое время я думал, что задача была NP-полной, если она (1) NP-сложная и (2) в NP.
Однако в известной статье «Метод эллипсоидов и его последствия в комбинаторной оптимизации» авторы утверждают, что проблема дробного хроматического числа принадлежит NP и является NP-сложной, но пока неизвестно, что она NP-полная. На третьей странице статьи авторы пишут:
... отметим, что задача упаковки вершин графа в некотором смысле эквивалентна проблеме дробных хроматических чисел, и прокомментируем явление, что эта последняя проблема является примером задачи в которая является N P- трудной но (на данный момент) не известен как N P -полный.
Как это возможно? Я упускаю тонкую деталь в определении NP-полной?
источник