Describe nondeterministic polynomial time algorithm

Assignment Help Computer Network Security

Reference no: EM13718895

1. The 3-Partition problem is defined as follows. Given a finite set A of 3m elements, a bound B ? Z⁺ (a positive integer) and a size s(a) ? Z⁺ for each element a ? A such that s(a) satisfies the following inequalities: B/4 < s(a) < B/2 and such that

_a?A∑ s(a) = mB.

Can A be partitioned into m disjoint sets S₁, S₂, ..., S_m such that, for 1 ≤ i ≤ m,

_a?S∑ s(a) = B?

Describe a nondeterministic polynomial time algorithm for this problem.

(d) If Professor Weise arrives at describing a deterministic polynomial algorithm for any of the above problems, what conclusions would you draw? Justify your answer.

Reference no: EM13718895

Questions Cloud

Evaluate the time required to reach the desired probability : The desired final population of a microbial population is a probability of 0.00058. If the initial population is 5 X 104. Estimate the time required to reach the desired probability at 110oC.

Calculate the velocity of contaminant migration : A sodium choride (non-reactive, inert) spill has entered a water-table aquifer. Determine the velocity of contaminant migration and time for spill to reach the drinking water well (years)?

How old was the sample in years : The amount of carbon present after t years is given by the exponential equation A = A0ekt, with k=-(ln2/5600). How old was the sample in years?

Determine mean and standard deviation of given variable : Determine the mean and standard deviation of the variable x in the binomial distribution where n=5 and pi=0.20. Determine the mean.

Describe nondeterministic polynomial time algorithm : How would you go about proving that the above two problems are indeed NP-Complete and describe a nondeterministic polynomial time algorithm for problem.

Determine the entropy of black-body radiation : Give an expression for the internal energy of the radiation and show that the entropy of black-body radiation in the Universe increases in time as T3/4.

Evaluate the ph of the buffer solution : You have 50 mL of a buffer solution that is 0.15 M in HA and 0.25 M in A. Calculate the pH of the solution after you add 100 mL of 0.01 M HCl to the solution. The pKa of HA is 4.75.

Find quantity of carbon dioxide in a container : How many grams of carbon dioxide (CO2) are found in a 15.2 L container under 1.5 atm and 20.0oC.

Explore the potentiometric titration : Why is it unnecessary to titrate to the precise position of the equivalence point when performing a potentiometric titration?

User Account

All Pages