Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Nordh, Gustav"'
Autor:
Lagerkvist, Victor, Nordh, Gustav
Uniqueness quantification ($\exists !$) is a quantifier in first-order logic where one requires that exactly one element exists satisfying a given property. In this paper we investigate the strength of uniqueness quantification when it is used in pla
Externí odkaz:
http://arxiv.org/abs/1906.07031
Autor:
Nordh, Gustav
The subject of this note is a challenging conjecture about X-rays of permutations which is a special case of a conjecture regarding Skolem sequences. In relation to this, Brualdi and Fritscher [Linear Algebra and its Applications, 2014] posed the fol
Externí odkaz:
http://arxiv.org/abs/1707.03928
Autor:
Nordh, Gustav
We investigate the power of non-deterministic circuits over restricted sets of base gates. We note that the power of non-deterministic circuits exhibit a dichotomy, in the following sense: For weak enough bases, non-deterministic circuits are no more
Externí odkaz:
http://arxiv.org/abs/1705.03263
Autor:
Nordh, Gustav
We present a framework for studying circuit complexity that is inspired by techniques that are used for analyzing the complexity of CSPs. We prove that the circuit complexity of a Boolean function $f$ is characterized by the partial polymorphisms of
Externí odkaz:
http://arxiv.org/abs/1609.04274
Autor:
Nordh, Gustav
Ladner’s theorem states that if P ≠ NP, then there are problems in NP that are neither in P nor NP-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in NP. Csp(Γ) problems are of the form: given a set o
Externí odkaz:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-8822
We study a family of problems, called \prob{Maximum Solution}, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e. res
Externí odkaz:
http://arxiv.org/abs/cs/0602047
Autor:
Nordh, Gustav
A Skolem sequence is a sequence a_1,a_2,...,a_2n (where a_i \in A = {1,...,n }), each a_i occurs exactly twice in the sequence and the two occurrences are exactly a_i positions apart. A set A that can be used to construct Skolem sequences is called a
Externí odkaz:
http://arxiv.org/abs/math/0506155
Publikováno v:
In Journal of Computer and System Sciences March 2017 84:52-78
Publikováno v:
In Theoretical Computer Science 24 May 2015 581:67-82