Although certain NP-complete problems stay hard even on average input, some NP-complete problems are only hard in rare cases. Such NP-complete problems can provably be resolved very quickly on average case under some probability distributions over all possible inputs. **1. What is the average case of a real-world graph ? ** **2. How to properly define a suitable probability distribution for real-world graphs ? **
Sergey Kirgizov at 2019-09-26 14:10:14
Edited by Sergey Kirgizov at 2019-09-26 14:18:52

Please consider to register or login to comment on the paper.