Results 11 to 20 of about 1,545,213 (249)
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem [PDF]
Logical Methods in Computer Science, 2012 The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise ...
Libor Barto, Marcin Kozik
doaj +1 more source
The complexity of global cardinality constraints [PDF]
Logical Methods in Computer Science, 2010 In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified constraints. A global cardinality constraint is an additional requirement that prescribes how many variables must be assigned a ...
Andrei A. Bulatov, Daniel Marx
doaj +1 more source
Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator [PDF]
Logical Methods in Computer Science, 2012 For an NP intersect coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function.
Jan Krajíček
doaj +1 more source
A Study of $k$-dipath Colourings of Oriented Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We examine $t$-colourings of oriented graphs in which, for a fixed integer $k \geq 1$, vertices joined by a directed path of length at most $k$ must be assigned different colours. A homomorphism model that extends the ideas of Sherk for the case $k=2$ is
Christopher Duffy +2 more
doaj +1 more source
Quasipolynomial Normalisation in Deep Inference via Atomic Flows and Threshold Formulae [PDF]
Logical Methods in Computer Science, 2016 Je\v{r}\'abek showed that cuts in classical propositional logic proofs in deep inference can be eliminated in quasipolynomial time. The proof is indirect and it relies on a result of Atserias, Galesi and Pudl\'ak about monotone sequent calculus and a ...
Paola Bruscoli +3 more
doaj +1 more source
A feasible interpolation for random resolution [PDF]
Logical Methods in Computer Science, 2017 Random resolution, defined by Buss, Kolodziejczyk and Thapen (JSL, 2014), is a sound propositional proof system that extends the resolution proof system by the possibility to augment any set of initial clauses by a set of randomly chosen clauses (modulo ...
Jan Krajicek
doaj +1 more source
Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceA path graph is the intersection graph of paths in a tree. A directed path graph is the intersection graph of paths in a directed tree. Even if path graphs and directed path graphs are characterized very similarly, their recognition algorithms differ ...
Lorenzo Balzotti
doaj +1 more source
On Minimum Maximal Distance-k Matchings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$
Yury Kartynnik, Andrew Ryzhikov
doaj +1 more source
Some theorems on passing from local to global presence of properties of functions [PDF]
Logical Methods in Computer Science, 2017 When given a class of functions and a finite collection of sets, one might be interested whether the class in question contains any function whose domain is a subset of the union of the sets of the given collection and whose restrictions to all of them ...
Dimiter Skordev
doaj +1 more source
Polynomial Size Analysis of First-Order Shapely Functions [PDF]
Logical Methods in Computer Science, 2009 We present a size-aware type system for first-order shapely function definitions. Here, a function definition is called shapely when the size of the result is determined exactly by a polynomial in the sizes of the arguments.
Olha Shkaravska +2 more
doaj +1 more source