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 http://www.cs.berkeley.edu/~christos/papers/ 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.
login/create account
Drupal
CSI of Charles University
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 http://www.cs.berkeley.edu/~christos/papers/ 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.