Finding hardness reductions automatically using SAT solvers

Helena Bergold, Manfred Scheucher, Felix Schröder

In this article, we show that the completion problem, i.e. the decision problem whether a partial structure can be completed to a full structure, is NP-complete for many combinator…