The problems are in PPP and PPA, respectively

Both this problem and the Smith/2nd Hamiltonian Path problems were suggested by Papadimitriou in his 1991 paper 'On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence". (See for a copy of the journal version.)

These problems are in natural complexity classes related to though apparently somewhat larger than PPAD . The subset sum problem is in the class PPP and the Smith problem is in the class PPA. Neither is known to be complete for the respective complexity class as far as I know.


Comments are limited to a maximum of 1000 characters.
More information about formatting options