Are there any "natural problems" which are known to be NPI under weak assumptions. By weak assumptions I mean something like $P \neq NP$ or $NP \neq Co-NP$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ cstheory.stackexchange.com/a/7854/32254 mentions an example under the assumption that P != NP, but I suppose it's not considered "natural". $\endgroup$– Albert HendriksJun 19, 2020 at 16:50
-
$\begingroup$ The same question was asked here: cstheory.stackexchange.com/questions/79/… $\endgroup$– Albert HendriksJun 19, 2020 at 18:10
Add a comment
|