Timeline for How do distributed applications verify that the data was processed correctly?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20, 2015 at 8:23 | comment | added | Rein Henrichs | @gnasher729 That's a good point. Sometimes the NP-complete version of a problem isn't very interesting. | |
| Sep 19, 2015 at 22:21 | comment | added | gnasher729 | True for NP-complete problems. But for example for the travelling salesman problem, the NP-complete problem is "is there a tour of 639 miles or less" which can be verified. The real problem "what is the shortest tour" is not a YES/NO problem and doesn't belong to the class NP. | |
| Sep 19, 2015 at 20:18 | history | edited | Rein Henrichs | CC BY-SA 3.0 | deleted 16 characters in body |
| Sep 19, 2015 at 20:12 | history | edited | Rein Henrichs | CC BY-SA 3.0 | deleted 1 character in body |
| Sep 19, 2015 at 20:06 | history | answered | Rein Henrichs | CC BY-SA 3.0 |