On NP-Complete Search Problems on Finite Algebras
Bernardo Rossi, Erhard Aichinger · 2024
We investigate under which structural assumptions on a finite algebra A the problem 3SAT with complexity measure the number of clauses can be reduced to$\text{POLSAT }(\mathrm{A})$in logarithmic space and with a linear growth of the problem size. Our results imply that under the exponential time hypothesis, no two-element algebra of tame congruence theory type 3 has a sub-exponential algorithm to solve a single polynomial equation.