Raghavendra's famous result from 2008 fully characterizes the inapproximability of every maximum constraint satisfaction problem (Max-CSP). However, the result inherently loses perfect completeness.
"Paper: Yuchen Zhang, John C Duchi, Michael I Jordan, Martin J Wainwright, Information-theoretic lower bounds for distributed statistical estimation with communication constraints"
Paper: Nachum Dershowitz and Yuri Gurevich, "A Natural Axiomatization of Computability and Proof of Church's Thesis" https://doi.org/10.2178/bsl/1231081370
Over the past few decades, probabilistic models have become an important tool for under-standing risks and decision making in practical financial systems.
A p-random restriction is a random partial input obtained by independently leaving each input variable unset with probability p setting them to either 0,1 with (1-p)/2 each.