Первое наблюдение состоит в том, что наличие именно того, что вы спрашиваете, будет доказательством того, что поскольку это будет означать, что множество всех экземпляров не может быть решено за полиномиальное время.п≠ Nп
Однако, и я думаю, что именно это вы и имели в виду, мы можем немного поиграть с тем, что мы подразумеваем под словом «решено за полиномиальное время». Если мы имеем в виду под этим все бесконечные подмножества экземпляров, принадлежность которых к P, являются N P -полными, то по теореме Махани нет ответа ( http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute -to-mahaney.html ). Эта теорема утверждает , что нет NP-полной задачи не может быть разреженной , если P = N P . Теперь, взяв подмножество экземпляров { 0 i ∣ i ∈ N } , мы имеем бесконечное разреженное подмножество экземпляров, для которых проверочное членство находится вφпNпп= Nп{0i∣i∈N} который не может быть N P -завершенным, если P = N P по теореме Махани.PNPP=NP