If you want to make money online : Register now

[Solved]: Does the Bible solve an NP-hard problem?

, , No Comments
Problem Detail: 

In the Bible, a census is taken of the 12 tribes of Israel:

Simeon: 59,300 Levi: 22,000 Judah: 74,600 Issachar: 54,400 Joseph: 72,700 Benjamin: 35,400 Reuben: 46,500 Gad: 45,650 Asher: 41,500 Zebulun: 57,400 Dan: 62,700 Naphtali: 53,400

In the book of Deuteronomy 27: 12-13, the tribes are partitioned into two groups, the first group consisting of Simeon, Levi, Judah, Issachar, Joseph, Benjamin, and the second group consisting of Reuben, Gad, Asher, Zebulun, Dan, Naphtali.

Someone mentioned to me that this particular partition is the optimal in the sense that it minimizes the absolute value of the total number of people in the first group minus the total number of people in the second group. This partition problem is an NP-hard problem. http://en.wikipedia.org/wiki/Partition_problem

Is this calculation correct?

Asked By : Craig Feinstein

Answered By : mhum

The partition provided in that passage is not optimal:

(Simeon + Levi + Judah + Issachar + Joseph + Benjamin) - (Reuben + Gad + Asher + Zebulun + Dan + Naphtali) = 318400 - 307150 = 11250

(Asher + Benjamin + Joseph + Reuben + Simeon + Zebulun) - (Dan + Gad + Issachar + Judah + Levi + Naphtali) = 312800 - 312750 = 50

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28047

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback