Record link: 
http://hdl.handle.net/20.500.12708/191346
-
Title: 
Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep
en
Citation: 
Pinsker, M. (2022). Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep. In 2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL) (pp. 80–87). IEEE. https://doi.org/10.1109/ISMVL52857.2022.00019
-
Publisher DOI: 
10.1109/ISMVL52857.2022.00019
-
Publication Type: 
Inproceedings - Keynote Contribution
en
Language: 
English
-
Authors: 
Pinsker, Michael 
-
Organisational Unit: 
E104-01 - Forschungsbereich Algebra 
-
Published in: 
2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL) 
-
ISBN: 
978-1-6654-2395-3
-
Date (published): 
24-Jun-2022
-
Event name: 
2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL) 
en
Event date: 
18-May-2022 - 20-May-2022
-
Event place: 
Dallas, United States of America (the)
-
Number of Pages: 
8
-
Publisher: 
IEEE, Piscataway
-
Keywords: 
canonical function; constraint satisfaction; finitely bounded homogeneous structure; local consistency; omega-categoricity; Ramsey structure; sheep
en
Abstract: 
A Constraint Satisfaction Problem (CSP) is a computational problem where we are given variables and constraints about them; the question is whether the variables can be assigned values such that all constraints are satisfied. We give an overview of the current state of research on CSPs where values for the variables and constraints are taken from a finitely bounded homogeneous structure which is fixed beforehand. We explain the main mathematical ideas so far, the three dilemmas they brought upon us, and what could be done to overcome them in order to obtain a satisfactory understanding of the computational complexity of such CSPs.
en
Research Areas: 
Mathematical and Algorithmic Foundations: 50%
Computer Science Foundations: 50%
-
Science Branch: 
1020 - Informatik: 5%
1010 - Mathematik: 95%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

37
checked on Jan 10, 2024

Google ScholarTM

Check