Constraints, MMSNP and expander relational structures (Q2439829): Difference between revisions

For a relational structure \(A\), let \(\mathrm{CSP}(A)\) be a class of relational structures \(B\) of the same type as \(A\) such that a relational homomorphism from \(B\) into \(A\) exists. The girth of a relational structure \(A\) is the length of a shortest cycle from \(A\). For a relational type \(\tau\) and positive integers \(k\) and \(t\), a polynomial-time algorithm \(\mathcal A\) is presented such that for a relational structure \(S\) of type \(\tau\) it constructs a relational structure \(\mathcal A(S)\) of type \(\tau\) with girth at least \(k\) and \(\mathcal A(S)\in\mathrm{CSP}(S)\) such that for every relational structure \(T\) of type \(\tau\) and size at most \(t\) we have \(S\in\mathrm{CSP}(T)\) if and only if \(\mathcal A(S)\in\mathrm{CSP}(T)\). It is proved that the complexity classes CSP and Monotone Monadic Strict NP are computationally equivalent. For a relational type \(\tau\), a positive integer \(k\) and \(\epsilon>0\), the author gives a polynomial-time construction of an \(\epsilon\)-expander of type \(\tau\) with girth at least \(k\) of size \(n\) for sufficiently large \(n\). As a technical tool, a twisted product is introduced which is a generalization of the zig-zag product.