5 papers · 1 filter
Nonuniform Deterministic Finite Automata over finite algebraic structures
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these aut…
Complexity of Modular Circuits
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
We study how the complexity of modular circuits computing AND depends on the depth of the circuits and the prime factorization of the modulus they use. In particular our constructi…
Equation satisfiability in solvable groups
Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski +1
The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell (2002) where they showed that this problem is in poly…
Intermediate problems in modular circuits satisfiability
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
In arXiv:1710.08163 a generalization of Boolean circuits to arbitrary finite algebras had been introduced and applied to sketch P versus NP-complete borderline for circuits satisfi…
Satisfiability in multi-valued circuits
Paweł M. Idziak, Jacek Krzaczkowski
Satisfiability of Boolean circuits is among the most known and important problems in theoretical computer science. This problem is NP-complete in general but becomes polynomial tim…