We (claim to) prove the extremely surprising fact that NP=RP. It is achieved by creating a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) for approximately counting the number of independent sets in bounded degree graphs, with any fixed degree bound, which is known to imply NP=RP. While our method is rooted in the well known Markov Chain Monte Carlo (MCMC) approach, we overcome the notorious problem of slow mixing by a new idea for generating a random sample from among the independent sets. A key tool that enables the result is a solution to a novel sampling task that we call Subset Sampling. In its basic form, a stationary sample is given from the (exponentially large) state space of a Markov chain, as input, and we want to transform it into another stationary sample that is conditioned on falling into a given subset, which is still exponentially large. In general, Subset Sampling can be both harder and easier than stationary sampling from a Markov chain. It can be harder, due to the conditioning on a subset, which may have more complex structure than the original state space. But it may also be easier, since a stationary sample is already given, which, in a sense, already encompasses “most of the hardness” of such sampling tasks, being already in the stationary distribution, which is hard to reach in a slowly mixing chain. We show that it is possible to efficiently balance the two sides: we can capitalize on already having a stationary sample from the original space, so that the complexity of confining it to a subset is mitigated. We prove that an efficient approximation is possible for the considered sampling task, and then it is applied recursively to create the FPRAS.
More like this (3)
This is part 1 of a series of blog posts about MCMC techniques: Markov chain Monte...This is part 1 of a series of blog posts about MCMC techniques: Markov chain Monte Carlo (MCMC) is a powerful class of methods to sample from probability distributions known only up to an (unknown) normalization constant. But before we dive into MCMC, let’s consider why you might want to do sampling in the first pla...
Artificial intelligence, or AI, refers to the ability of tools or technology to perform tasks that...Artificial intelligence, or AI, refers to the ability of tools or technology to perform tasks that would normally require human intelligence to complete. Machine learning is a subset of AI in the computer science space – where the platform or model learns from an existing data set so that it can understand the under...
Karl Friston wanted me to know he had plenty of time. That wasn’t quite true. He...Karl Friston wanted me to know he had plenty of time. That wasn’t quite true. He just didn’t want our conversation—about his passion, the physics of mental life—to end. Once it did, he would have to step outside, have a cigarette, and get straight back to modeling COVID-19. I caught the University College London neuroscientist at 6 p.m., his time, just after he had...