Search Results

Given as input an integer $n$ and a set $S$ of sets of elements of $\{1, ..., n\}$, what is the complexity of finding a set $T$ of elements of $\{1, ..., n\}$ such that $T$ has minimal cardinality and …

The following answer doesn't really answer the question given, because it's not about counting spanning subgraphs but about counting all subgraphs where some edges are fixed (i.e., cannot be removed). …

The problem is #P-hard, as we prove in a recent preprint: https://arxiv.org/abs/1908.07093 The way the preprint is phrased is closer to the equivalent formulation of the problem given at the end of m …

The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \b …

I show a reduction from positive partitioned 2-DNF assignment counting (see proof of 5.1 in [http://www.vldb.org/conf/2004/RS22P1.PDF] for details and inspiration of my proof). This problem asks to co …

For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call $L$-INTERLEAVING: Input: two words $u, v \in A^*$ Output: whether there exists an interleaving of $u …

Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a (non-contiguous …

Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, …

The standard NP-hard SAT problem is the problem of Boolean satisfiability of conjunctions of clauses, where clauses are disjunctions of literals. I am interested in the problem of the Boolean satisfi …

Exact SAT (XSAT) is NP-hard by a reduction from the exact hitting set problem (or, equivalently, exact set cover), even when all literals are positive. Encode the set $X$ to a set of positive literals …

With an idea by Louis Jachiet, we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the $b$'s by decreasing "ending time" (i.e., …

OK, I'm coming back to this after some more thought based on the ideas of @GaraPruesse and @ChandraChekuri. I'm not 100% sure, because these arguments are a pain to formalize and visualize, but I thin …

If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. ( …

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct in …

A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time). …