In this talk, A is an NP-predicate, that is:
- y ∈ A(x, _) can be tested in polynomial time.
- y is of size polynomial in the size of x.
Many natural problems have this property:
- Enumerate the answer set of a database query Q on database 𝔻
- Enumerate the transversals of a hypergraph ℋ