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 1 week 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.

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.

Explain the 3 primary ingredients of Just in Time and how it can be used in...

Explain the 3 primary ingredients of Just in Time and how it can be used in a transportation company.

2. How has e-business transformed marketing? a. Explain how social networking and the "wisdom of crowds”...

2. How has e-business transformed marketing? a. Explain how social networking and the "wisdom of crowds” help companies improve their marketing. b. Define how behavioral targeting and explain how it works at individual Web sites and on advertising networks. c. Define the social graph and explain how it is used in e-commerce marketing.

Subjects