4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    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
    Oct 8, 2016 at 18:56
  • $\begingroup$ mathoverflow.net/questions/34889/… $\endgroup$
    – Thomas Klimpel
    Oct 9, 2016 at 23:38

1 Answer 1

Reset to default
3
$\begingroup$

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}$.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.