Hardness of Counting Orderings: Taking Gadget Amplification to the Limit

Marcelo Arenas, María Alejandra Schild, Bernardo Subercaseaux

We introduce a new elementary technique for proving $\#P$-hardness results under Turing reductions, and showcase its applicability by settling the counting complexity of several fu…