Wednesday, May 11, 2011

CrazyEngineers Forum - Computer Science & IT Engineering

CrazyEngineers Forum - Computer Science & IT Engineering

List of unsolved problems in Computer Science

Posted: 10 May 2011 09:26 AM PDT

Let's list down the unsolved problems in Computer science.

1. P = NP
2. One way functions

What are the other yet to be solved problems?

Is there a solution to the Two Army Problem?

Posted: 10 May 2011 09:19 AM PDT

While studying Transport Layer's 'releasing a connection' topic, I came across the famous 'Two Army Problem'

Imagine that one army (say white army) is encamped in a valley. On both the surrounding hill sides is opposite army (say blue army). The white army is larger than either of the blue armies alone, but together they are larger than the white army.
If either blue army attacks by itself , it will be defeated but if the blue armies attack simultaneously, they will be victorious.

The blue armies want to synchronize their attacks. However, their only communication medium is to send messages on foot down into the valley, where they might be captured and the message is lost.
The question is: Does a protocol exist that allows the blue armies to win?

It's been proven that no such protocol exists that works. Any ideas?
Attached Images
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)