4 ms·

Can someone explain to me why this is important. From the outset it's clear that there will always be a chance of failure and the two generals can never be cer

Can someone explain to me why this is important. From the outset it's clear that there will always be a chance of failure and the two generals can never be certain. Why does it matter that this proof exists. Or is there something that's non-obvious here.

lincolnq 16y ago
It's an important impossibility result like the Halting Problem. You can be led down the wrong path for hours designing protocols which attempt to solve an unsolvable problem but do so in a seemingly-almost-correct way -- until the complexity is so great that you can't understand where it goes wrong. If you didn't have these results, you might be tempted to believe your solution at that point was correct. With this result you can be sure it's wrong, recognize the pattern of unsolvability, and give up much sooner.
- ScotterC 16y ago
  That makes a lot of sense. But also just goes to show how effective preliminary design work can be for making a smoother overall production curve. Still, one can easily get lost in it if they don't step back every once in awhile and realize their beating their heads against a wall.
  - paulgb 16y ago
    As a side-note, the way I came across the problem was that yesterday I was trying to change the location of a date and my text messages were not always getting through (possibly due to my proximity to the G20 cell jamming). I realized that there was no way to know for sure, by text messages, whether we both committed to the change. (fortunately it worked out anyway)
- ryanjmo 16y ago
  This is the same value of NP-Reductions. They let you know that you should not try to solve the problem directly (because you can solve the problem without showing P=NP). Thus you know your approach should rather use techniques like approximations or high speed SAT solvers.
  - lukev 16y ago
    Although it should be pointed out that since P=NP has never been proven false, there is theoretically a chance of success. And if such a thing were possible, it's most likely that it would happen by looking at a new form of an NP-complete problem that might give some new mental handholds on the problem, rather than SAT itself. Just saying.
    - ryanjmo 16y ago
      Yes, but the point is with very very high probability YOU are not going to be the one to solve P vs. NP, so you shouldn't waste your time. On a side note, I really hate when people get voted up for bringing up things that do not have realistic probabilities associated with them.
rlpb 16y ago
As a real world example: Synctus depends on being able to do this correctly (what it does is described at http://www.synctus.com/tech/ http://www.synctus.com/tech/ and the right hand column at http://www.synctus.com/tech/locking.html http://www.synctus.com/tech/locking.html) - consider how the lock transfer might work in the context of the Two Generals' Problem. How exactly I do it is currently a trade secret. I've worked around the problem, but the issues surrounding this are a big part of the solution.

lincolnq 16y ago

It's an important impossibility result like the Halting Problem. You can be led down the wrong path for hours designing protocols which attempt to solve an unsolvable problem but do so in a seemingly-almost-correct way -- until the complexity is so great that you can't understand where it goes wrong. If you didn't have these results, you might be tempted to believe your solution at that point was correct. With this result you can be sure it's wrong, recognize the pattern of unsolvability, and give up much sooner.

ScotterC 16y ago
That makes a lot of sense. But also just goes to show how effective preliminary design work can be for making a smoother overall production curve. Still, one can easily get lost in it if they don't step back every once in awhile and realize their beating their heads against a wall.
- paulgb 16y ago
  As a side-note, the way I came across the problem was that yesterday I was trying to change the location of a date and my text messages were not always getting through (possibly due to my proximity to the G20 cell jamming). I realized that there was no way to know for sure, by text messages, whether we both committed to the change. (fortunately it worked out anyway)
ryanjmo 16y ago
This is the same value of NP-Reductions. They let you know that you should not try to solve the problem directly (because you can solve the problem without showing P=NP). Thus you know your approach should rather use techniques like approximations or high speed SAT solvers.
- lukev 16y ago
  Although it should be pointed out that since P=NP has never been proven false, there is theoretically a chance of success. And if such a thing were possible, it's most likely that it would happen by looking at a new form of an NP-complete problem that might give some new mental handholds on the problem, rather than SAT itself. Just saying.
  - ryanjmo 16y ago
    Yes, but the point is with very very high probability YOU are not going to be the one to solve P vs. NP, so you shouldn't waste your time. On a side note, I really hate when people get voted up for bringing up things that do not have realistic probabilities associated with them.

rlpb 16y ago

As a real world example: Synctus depends on being able to do this correctly (what it does is described at http://www.synctus.com/tech/ http://www.synctus.com/tech/ and the right hand column at http://www.synctus.com/tech/locking.html http://www.synctus.com/tech/locking.html) - consider how the lock transfer might work in the context of the Two Generals' Problem. How exactly I do it is currently a trade secret. I've worked around the problem, but the issues surrounding this are a big part of the solution.