next up previous
Next: NON DETERMINISTIC ALGORITHM Up: P and NP Previous: P and NP

Partition

Instance Set tex2html_wrap_inline259 with sizes tex2html_wrap_inline261

Question Is there a subset tex2html_wrap_inline263 such that tex2html_wrap_inline265 ?

Partition tex2html_wrap_inline278 NP gueses, check, time O(n). It is known that Partition tex2html_wrap_inline282 .

Dynamic Programming Solution:
Let tex2html_wrap_inline273 denote the truth value of the statement: "there is a subset of tex2html_wrap_inline275 for which the sum of the in size is exactly j".
tex2html_wrap_inline277

First Row tex2html_wrap_inline279

figure91

eqnarray96

tex2html_wrap_inline281
else Partition tex2html_wrap_inline283
tex2html_wrap_inline285 Must be careful about input size of an instance


Sushil Prasad
Thu May 13 13:03:52 EDT 1999