4.16.1 3D Matching

Definition

Given disjoint sets ,,, each of size n and a set T ⊆×× of triples, does there exist a set of n triples in T such that each element of ∪∪ is in exactly one of these triples?

Polynomial Certifier

Given disjoint sets ,,, each of size n and a set T ⊆×× of triples, does there exist a set of n triples in T such that each element of ∪∪ is in exactly one of these triples?

• Input: Given disjoint sets ,,, each of size n
• Certificate: a set T
• Certifier: Check for ,, that if any of their elements has appeared more than once in T.
• Time Complexity: O(n² + n² + n²) = O(n²).

Reduction from 3-SAT by encoding with gadget