It is conjectured that $NP\cap CoNP$ does not have a complete problem with respect to the polynomial-time many-to-one reductions. I would like to know the current knowledge about the nonuniform versions of this question:

Q1. Does $(NP\cap CoNP)/poly$ have a complete problem with respect to the $P/poly$ many-to-one reductions?

A related question is about the existence of a universal representation of $$(NTIME(n^a)\cap CoNTIME(n^a))/n^b.$$ where $a$ and $b$ are arbitrary fixed constants. By a universal representation, I mean the existence of a function $$f(e,x)\in (NTIME(n^c)\cap CoNTIME(n^c))/n^d$$ for some fixed $c$ and $d$ ($|e|=|x|^w$ for a fixed $w$) such that for every $$g(x)\in (NTIME(n^a)\cap CoNTIME(n^a))/n^b,$$ we have $$\forall n\in\mathbb{N},\exists e_n\in\{0,1\}^{n^w},\forall x\in\{0,1\}^n\: f(e_n,x)=g(x).$$

Does such a representation exist?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.