Question

In: Advanced Math

How to proof that the 2-partition problem can be transformed to 3-partition problem and the time...

How to proof that the 2-partition problem can be transformed to 3-partition problem and the time complexity of the transformation

(i.e. the 2-partition problem can be solved by using an algorithm that solves the 3-partition problem)

Solutions

Expert Solution

A most common mistake is to believe that the polynomial reduction used is in theory of the complexity to define NP completeness does preserve the strong sense. This is completely false :

By definition of NP-complete, ANY NP-complete problem can be reduced to ANY other NP-complete problem.

A reduction from a NP-complete problem in tre strong sense, say 3-Partition, does not prove that your problem is NP-complete in the strong sense. It simply proves that your problem is NP-complete. In particular there does exist a reduction from 3-PARTITION to PARTITION.

- Conversely a reduction from a NP-complete problem in the ordinary sense does not prevent your problem to be NP complete in the strong sense. In particular there does exist a reduction from PARTITION to 3-PARTITION.

To preserve the strong sense, you need more than the usual reduction. In their book Garey & Johnson define around page 100 the notion of pseudo-polynomial reduction for this purpose. Basically it ensures that in the transformation, the maximum value does not grow exponentially and the size of the encoding is not shrink exponentially.

Colby Messinger answered 4 months ago
Next > < Previous

Related Solutions

Prove that the partition problem is NP-complete by giving a polynomial time reduction of the subset-sum...
Prove that the partition problem is NP-complete by giving a polynomial time reduction of the subset-sum problem to the partition problem.
The PARTITION INTO PATHS OF LENGTH 2 problem is as follows: INSTANCE: A graph, G =...
The PARTITION INTO PATHS OF LENGTH 2 problem is as follows: INSTANCE: A graph, G = (V, E) with IV| = 3q for a positive integer q. QUESTION: Is there a partition of V into q disjoint subsets VI, V2, ..., Vq of 3 vertices such that, for each V1 = {Vi[1], Vi[2], Vi[3), at least two of the three edges {Vi[1], Vi[2], {Vi[1], Vi[3], and {Vi[2], Vi[3]} belong to E? Prove the PARTITION INTO PATHS OF LENGTH 2 problem...
3. Problem 3: How much time has elapsed? Unix time is commonly used to track the...
3. Problem 3: How much time has elapsed? Unix time is commonly used to track the amount of time that has passed in computer systems. The Unix time is stored as the number of seconds that have passed since 00:00:00 UTC January 1, 1970. However, the number of seconds by itself is not directly meaningful to most users, but luckily for us the number of seconds elapsed provides sufficient information to infer what we may need to display to an...
Problem 3 Look back on the data from Problem 2 regarding the time required to perform...
Problem 3 Look back on the data from Problem 2 regarding the time required to perform a repetitive task (in seconds) on an assembly line for Farnsworth (the seasoned employee) and Higgenbottom (the newby). The times are shown in chronological order. a. Find a 95% confidence interval for the standard deviation of times for Farnsworth. Do the same for Higgenbottom. What do these confidence intervals indicate? b. Given that these times are listed chronologically, how useful are the confidence intervals...
Problem 2: Bertrand or Monopoly? How can you tell? After your time in Collegeville, you move...
Problem 2: Bertrand or Monopoly? How can you tell? After your time in Collegeville, you move on to Adultville - a much bigger town. You are again the economic advisor to the mayor of Adultville. You see that in Adultville there is only one firm selling widgets, and that Q = 25, P= 20, and ϵ = −2. You also know (from your predecessor) that demand is linear, Q = A − BP, and that the technology for producing widgets...
2. Describe how energy contained in coal is transformed into electric energy, how it gets to...
2. Describe how energy contained in coal is transformed into electric energy, how it gets to your home, and then how it is converted into energy in the forms that you need. Be as detailed in each stage as you can.
Write a combinatorial proof for 1 n + 2 ( n − 1 ) + 3...
Write a combinatorial proof for 1 n + 2 ( n − 1 ) + 3 ( n − 2 ) + ⋯ + ( n − 1 ) 2 + n 1 = ( n + 2 choose 3 ) .
How far has the United States transformed itself in time in dealing with the subjects/topics covered...
How far has the United States transformed itself in time in dealing with the subjects/topics covered in Chapter 5: Civil Rights. Is the U.S. on the 'right or wrong track' and support your argument as to how you reached that conclusion.
4. Give a detailed example of how one's sensory memory can be effectively transformed into the...
4. Give a detailed example of how one's sensory memory can be effectively transformed into the following three types of long-term memory: (a) semantic memory, (b) episodic memory and (c) procedural memory. [20%]
Demonstrate how data from an IoT device can be transformed into information and business intelligence.
Demonstrate how data from an IoT device can be transformed into information and business intelligence.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT