N queens counting as a rare event and a quantile integral, turned into a Monte Carlo program for P versus NP: NP = RP is shown equivalent to sampling queens completions, promise RP = promise P, which implies P = RP, is restated as a hitting set problem, with exact computations on the queens.
book monte-carlo nested-sampling rp n-queens-problem lorenz-curve approximate-counting rare-event-simulation p-versus-np derandomization randomized-complexity vertical-likelihood markov-chain-mixing
-
Updated
Oct 28, 2026 - TeX