(a) Suppose that a computer can calculate the weight of a single Hamiltonian pat

Question

(a) Suppose that a computer can calculate the weight of a single Hamiltonian path in Kn in 10-15 sec. (This means that it can compute the weight of a thousand trillion different cycles per second.) If you use this computer to chech all possible cycles, how long would it take to find the shortest (in total driving miles) cycle that visits all state capitals in the lower 48 United States?

(b) Now suppose the entire population of the earth (which we can round to 10 billion people) has a computer like the one described in the above question, and they all set about checking different possible cycles. How long would it take to check all possible cycles in K48?

answers in years

Explanation / Answer

(a)

In 1 sec it processes = 10^15

No. of combinations to be processed to find the shortest path = 48!

So time taken to process this = 48! / (10^15) seconds = 1.241392 x 10^46 seconds = 3.936427 x 10^38 years

(b)

With 10 billions comporter simultaneously working, time will reduce by 10 billions times

time taken to process this =1.241392 x 10^36 seconds = 3.936427 x 10^28 years

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.