سؤال

Suppose $coNP \neq NP$

language B would be called "complete" in $coNP-NP$ if:

  1. $B\in coNP - NP$
  2. $A\in coNP-NP \implies A\leq_pB$

Are there any "complete" languages in $coNP - NP$?

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top