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?

$\endgroup$
  • $\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 '16 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 '16 at 18:56
  • $\begingroup$ mathoverflow.net/questions/34889/… $\endgroup$ – Thomas Klimpel Oct 9 '16 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.