Almost Uniform Sampling of Independent Sets in Polynomial Time -- Implying NP=RP
András Faragó · arXiv (Cornell University) · 2023
We prove the unexpected result that almost uniform sampling of independent sets in graphs is possible via a probabilistic polynomial time algorithm. Note that our sampling algorithm (if correct) has extremely surprising consequences; the most important one being no less than the unlikely collapse NP=RP.