Title :
Constraint satisfaction problems on specific subsets of the n-dimensional unit cube
Author :
Levon Aslanyan;Hasmik Sahakyan;Hans-Dietrich Gronau;Peter Wagner
Author_Institution :
Institute for Informatics and Automation Problems, Yerevan, Armenia
Abstract :
Characterization of n-cube subsets is considered in terms of variable frequencies (differences) or in terms of hypergraphs - their degree sequences. Characterization under specific constraints is considered - those are the constraints of: upper sets, Sperner sets and random sets. Above the general knowledge about the subset characteristics like variable differences and degree sequences these specific classes are also characterized by sets of their properties - inclusion one into the other, reductions and complexity issues, example series and random descriptions. The issues considered are tightly related to the areas of computer tomography, theory of Boolean functions, (0,1) matrices, hypergraphs, and combinatorial set systems.
Keywords :
"Complexity theory","Boolean functions","Optimization","Finite element analysis","Electronic mail","Tomography","Probabilistic logic"
Conference_Titel :
Computer Science and Information Technologies (CSIT), 2015
DOI :
10.1109/CSITechnol.2015.7358249