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

You comment anonymously! You will not be able to edit/delete the comment.

Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. You can post public domain content. All user-generated content will be freely available online. Please see this page to learn more about Papersγ's terms of use and privacy policy.