The rough idea of these inapproximability results is to form a graph that represents a probabilistically checkable proof system for an NP-complete problem such as the Boolean satisfiability problem.
Ideea acestor rezultate de neaproximabilitate este de a forma un graf care reprezintă un sistem de demonstrații probabilistic verificabile pentru o problemă NP-completă, cum ar fi problema satisfiabilității booleene.