The fact that PPAD is a subclass of TFNP seems to be taken as evidence that PPAD cannot be shown complete (or hard) for classes of independent interest like NP ∩ coNP. Slightly confusing, it even seems to excuse that it has not yet been shown complete for PPA, in which it is contained and which has complete problems.
A hint why this is expected is given at the end of Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989):
Finally can we hope to have TFNP complete problems? As with other classes (such as NP ∩ coNP, R, BPP etc.) whose machine based definition is semantic instead of syntactic (i.e., depends on a property that the machine exhibits when computing on any input), we do not expect such problems to exist.
I had a similar experience with R (or rather RP) that I started to settle for completeness of smaller classes, until I suddenly realized that the lower end (first the compressed word problem for monoids, then the compressed word problem for free groups) was actually P-complete, i.e. I had wrongly believed that those would be hard problems.
How valid are such excuses really for failing to show completeness (or hardness) of "believed to be difficult" problems with respect to complexity classes of independent interest?
-
$\begingroup$ Another explanation, taken from the wiki on TFNP: "In contrast to FNP, there is no known recursive enumeration of machines for problems in TFNP. It seems that such classes, and therefore TFNP, do not have complete problems." Maybe this is what people actually mean when they say semantic class. $\endgroup$Thomas Klimpel– Thomas Klimpel2016年10月07日 09:31:40 +00:00Commented Oct 7, 2016 at 9:31
-
$\begingroup$ This reference might actually explain what is going on: M. Sipser, On relativization and the existence of complete sets, in "Proceedings, 9th ICALP, 1982." $\endgroup$Thomas Klimpel– Thomas Klimpel2016年10月08日 18:56:44 +00:00Commented Oct 8, 2016 at 18:56
-
$\begingroup$ mathoverflow.net/questions/34889/… $\endgroup$Thomas Klimpel– Thomas Klimpel2016年10月09日 23:38:23 +00:00Commented Oct 9, 2016 at 23:38
1 Answer 1
It is still open whether $\mathrm{NP\cap coNP=QP}$, where $\mathrm{QP=\cup_k2^{log^k(n)}}$.
And in this answer, we have shown that $\mathrm{QP}$ has no complete problem.
If now someone shows that $\mathrm{NP\cap coNP}$ has some complete problem, that would imply $\mathrm{NP\cap coNP\neq QP}$.