Leonid A. Levin: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Title: Leonid A. Levin | |||
Link to Article: https://arxiv.org/abs/ | Research Question: Can random instances of a graph coloring problem be hard on average? | ||
Methodology: The researchers used a random graph problem and introduced randomizing reductions to show the intractability of random instances of a graph coloring problem. | |||
Results: The researchers proved that the graph problem is hard on average unless all NP problems under all samplable distributions are easy. This poses significant technical difficulties. | |||
Implications: This work provides a strong hardness result related to "typical" or "average" instances of a problem, which is crucial for understanding the efficiency of algorithms and the P=NP question. It also shows that average case completeness of a random graph problem is unlikely without introducing randomizing reductions. | |||
Link to Article: https://arxiv.org/abs/0112001v9 | |||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0112001v9 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
[[Category: | [[Category:Problem]] | ||
[[Category: | [[Category:Graph]] | ||
[[Category: | [[Category:Random]] | ||
[[Category: | [[Category:Average]] | ||
[[Category: | [[Category:Instances]] | ||
Latest revision as of 03:43, 24 December 2023
Title: Leonid A. Levin
Research Question: Can random instances of a graph coloring problem be hard on average?
Methodology: The researchers used a random graph problem and introduced randomizing reductions to show the intractability of random instances of a graph coloring problem.
Results: The researchers proved that the graph problem is hard on average unless all NP problems under all samplable distributions are easy. This poses significant technical difficulties.
Implications: This work provides a strong hardness result related to "typical" or "average" instances of a problem, which is crucial for understanding the efficiency of algorithms and the P=NP question. It also shows that average case completeness of a random graph problem is unlikely without introducing randomizing reductions.
Link to Article: https://arxiv.org/abs/0112001v9 Authors: arXiv ID: 0112001v9