On NP-Complete Search Problems on Finite Algebras

Bernardo Rossi; Erhard Aichinger

doi:10.1109/ISMVL60454.2024.00034

On NP-Complete Search Problems on Finite Algebras

Bernardo Rossi
, Erhard Aichinger

Institute for Algebra

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

Abstract

We investigate under which structural assumptions on a ﬁnite 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 language	English
Title of host publication	2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL 2024)
Place of Publication	Los Alamitos, CA
Publisher	IEEE Computer Society
Pages	131-136
Number of pages	6
ISBN (Electronic)	9798350343083
ISBN (Print)	979-8-3503-4308-3
DOIs	https://doi.org/10.1109/ISMVL60454.2024.00034
Publication status	Published - May 2024

Publication series

Name	Proceedings of The International Symposium on Multiple-Valued Logic
ISSN (Print)	0195-623X

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

10.1109/ISMVL60454.2024.00034

Cite this

@inproceedings{0a85706c6c304abcba6bffa23a4e58a4,

title = "On NP-Complete Search Problems on Finite Algebras",

abstract = "We investigate under which structural assumptions on a ﬁnite 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.",

author = "Bernardo Rossi and Erhard Aichinger",

year = "2024",

month = may,

doi = "10.1109/ISMVL60454.2024.00034",

language = "English",

isbn = "979-8-3503-4308-3",

series = "Proceedings of The International Symposium on Multiple-Valued Logic",

publisher = "IEEE Computer Society",

pages = "131--136",

booktitle = "2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL 2024)",

}

On NP-Complete Search Problems on Finite Algebras. / Rossi, Bernardo; Aichinger, Erhard.
2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL 2024). Los Alamitos, CA: IEEE Computer Society, 2024. p. 131-136 (Proceedings of The International Symposium on Multiple-Valued Logic).

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

TY - GEN

T1 - On NP-Complete Search Problems on Finite Algebras

AU - Rossi, Bernardo

AU - Aichinger, Erhard

PY - 2024/5

Y1 - 2024/5

N2 - We investigate under which structural assumptions on a ﬁnite 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.

AB - We investigate under which structural assumptions on a ﬁnite 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.

UR - https://www.scopus.com/pages/publications/85203139655

U2 - 10.1109/ISMVL60454.2024.00034

DO - 10.1109/ISMVL60454.2024.00034

M3 - Conference proceedings

SN - 979-8-3503-4308-3

T3 - Proceedings of The International Symposium on Multiple-Valued Logic

SP - 131

EP - 136

BT - 2024 IEEE 54th International Symposium on Multiple-Valued Logic (ISMVL 2024)

PB - IEEE Computer Society

CY - Los Alamitos, CA

ER -

On NP-Complete Search Problems on Finite Algebras

Abstract

Publication series

Fields of science

JKU Focus areas

Access to Document

Other files and links

Equations in universal algebra

Cite this

On NP-Complete Search Problems on Finite Algebras

Abstract

Publication series

Fields of science

JKU Focus areas

Access to Document

Other files and links

Projects

Equations in universal algebra

Cite this