On NP-complete search problems on finite algebras

Bernardo Rossi, Erhard Aichinger

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

Abstract

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 PolSat(A) in logarithmic space and with a linear growth of the problem size.
Original languageEnglish
Title of host publication2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL 2024)
Place of PublicationLos Alamitos, CA
PublisherIEEE Computer Soc.
Pages131-136
Number of pages6
ISBN (Print)979-8-3503-4308-3
DOIs
Publication statusPublished - May 2024

Fields of science

  • 101 Mathematics
  • 101001 Algebra
  • 101005 Computer algebra
  • 101013 Mathematical logic
  • 102031 Theoretical computer science

JKU Focus areas

  • Digital Transformation

Access to Document

Cite this