Skip to main content
Computer Science

Return to Question

added 97 characters in body
Source Link
SmashTheStack
SmashTheStack
  • 155
  • 6

Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solvedcan be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

Source Link
SmashTheStack
SmashTheStack
  • 155
  • 6

Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?