4 ms·
I've alway been interested in this problem. I feel like information theory, Bayesian analysis including Markov chain monte carlo could give you some insight in
by sjg007 9y ago
I've alway been interested in this problem. I feel like information theory, Bayesian analysis including Markov chain monte carlo could give you some insight into the distribution of truth values for a satisfiable configuration especially around the phase transition. You can covert 3-SAT into a Bayesian network but exact inference is still NP complete.
There should be some higher order information in a graph of the k-SAT problem... But many of the algorithms here are still NPC (e.g. finding a clique).. So then you discover tree width (tree decomposition) as an approximation (also in Bayesian networks) and find out that it is quite useful but still doesn't quite help. It makes faster SAT solvers but we haven't found anything invariant yet.
Anyway I still enjoy thinking about the problem, my random ideas have taken on more structure based on diving into the different subjects and trying to use them on this problem. I find it fascinating that you can take something simple like these linear circuits and it turns out that they are not simple at all and that they scale through the different disciplines.