Известен ли какой-либо разреженный язык в NPI в предположении

Интересно знать погоду есть редкий язык (даже построен с задержкой diagolanization) в НПИ в предположении , что .$P \neq NP$

Я не знаю, задаете ли вы открытую проблему или она уже решена. Тем не менее, следующая статья может пролить свет на эту проблему:

Kurtz, SA 1985. Разреженные множества в NP-P: релятивизации. SIAM J. Comput. 14, 1 (февраль 1985 г.), 113-119. DOI = http://dx.doi.org/10.1137/0214008

В основном, это говорит о том, что, даже если предположить, что P ≠ NP, существует оракул, относительно которого не существует разреженных множеств в NP-P.

С другой стороны, следующая статья:

Т. Бейкер, Дж. Джилл и Р. Соловей, "Релятивизации вопроса P =? NP", SIAM J. Computing (1975), 431-442. DOI = http://dx.doi.org/10.1137/0204037

демонстрирует оракула, относительно которого существуют разреженные множества в NP-P.

$NPI \subset NP-P$

$E \neq NE$

Хартманис Дж., Сьюэлсон В. и Иммерман Н. 1983. Разреженные множества в NP-P: время выполнения и время ожидания. В материалах пятнадцатого ежегодного симпозиума ACM по теории вычислений STOC '83 . ACM, New York, NY, 382-391. DOI = http://doi.acm.org/10.1145/800061.808769

(Журнальная версия доступна здесь: http://dx.doi.org/10.1016/S0019-9958(85)80004-8 )