Scarf is Ppad-Complete

Details Scarf is Ppad-Complete Scarf is Ppad-Complete

2008-12-09

arxiv.org/abs/0812.1601v4

Computer Science

Computational Complexity

Scientific paper

Scarf's lemma is one of the fundamental results in combinatorics, originally introduced to study the core of an N-person game. Over the last four decades, the usefulness of Scarf's lemma has been demonstrated in several important combinatorial problems seeking "stable" solutions. However, the complexity of the computational version of Scarf's lemma (SCARF) remained open. In this paper, we prove that SCARF is complete for the complexity class PPAD. This proves that SCARF is as hard as the computational versions of Brouwer's fixed point theorem and Sperner's lemma. Hence, there is no polynomial-time algorithm for SCARF unless PPAD \subseteq P. We also show that fractional stable paths problem and finding strong fractional kernels in digraphs are PPAD-hard.

Affiliated with

Also associated with

No associations

Rating

Scarf is Ppad-Complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scarf is Ppad-Complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scarf is Ppad-Complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281645