Almost Uniform Sampling of Independent Sets in Polynomial Time -- Implying NP=RP

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.

Paper

Similar papers

© 2026 NYSGPT2525 LLC