# Tag Info

14

Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries". It seems that the existence of a polynomial time algorithm is still open. Schmulevich et al. prove that "Almost all ...

14

If every sequence has length 3, the problem is known as Betweenness. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version ...

12

With multiple copies of the same label allowed, the problem is NP-hard, via a reduction from cliques in graphs. Given a graph $G$ in which you want to find a $k$-clique, make a DAG with a source vertex for each vertex of $G$, a sink vertex for each edge of $G$, and a directed edge $xy$ whenever $x$ is a vertex of $G$ that forms an endpoint of edge $y$. Give ...

9

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec Divide the vertices into two groups - some will represent literals, the ...

7

In their paper Every Poset Has a Central Element, Linial and Saks show (Theorem 1) that the number of queries required to solve the ideal identification problem in a poset $X$ is at most $K_0 \log_2 i(X)$, where $K_0 = 1/(2 - \log_2(1 + \log_2 5))$ and $i(X)$ is the number of ideals of $X$. What they call an "ideal" is actually a lower set and there is an ...

7

This is not a complete answer, but it's too long to be a comment. I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight. Consider the following poset. The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable. (The Hasse diagram is a $4$-cycle). ...

7

Restrictions on pre-orders You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it would not be compatible with a pre-order in which $a \cong b$ (that is $a \leqslant b$ and $b \leqslant a$). We can achieve this by supplementing the pre-order ...

5

For the Boolean n-cube $(\{0, 1\}^n, \leq)$ (or, equivalently, for the poset $(2^S, \subseteq)$ of all subsets of an n-element set), the answer is given by Korobkov and Hansel's theorems (from 1963 and 1966, respectively). Hansel's theorem [1] states that an unknown monotone Boolean function (i.e., an unknown monotone predicate on this poset) can be learned ...

5

For the problem of finding all the maximal elements of $P$ over the lattice of subsets $2^{[n]}$, this amounts to exact inference of a positive boolean function of $n$ boolean variables. If you only care about the number of evaluations of $P$ (not the computational complexity), you can find a survey in Data Mining and Knowledge Discovery via Logic-Based ...

5

Every simplification order is indeed a well-partial order because of this simple statement: If $R$ is a well-quasi order, and $S$ is a partial order, and $R\subseteq S$, then $S$ is a well-partial order. Proof: Exercise. Note that this nice property is not true for well-founded orders in general! In this sense, well-quasi orders are much more "stable". ...

4

Surely, you want $s_1 < s_2$ if there is a $t$ such that $s_1.t < s_2.t$ and $s_1.u \leq s_2.u$ for every other field $u$. That, at least, gives you a well-founded order. But there are many other well-founded orders on tuples, e.g. lexicographical order for some order of the fields (though you might need a heuristic to find the order), and various ...

3

Here's a nice property of WQOs: If $R$ is a WQO on terms, and $S$ is another transitive relation such that $$R\ \subseteq\ S$$ Then $S$ is a WQO Proof: Let $t_1,\ldots, t_n,\ldots$ be an infinite sequence of terms. Because $R$ is a WQO, there are $i, j$ with $i<j$ such that $t_i\ R\ t_j$. But this implies $t_i\ S\ t_j$, so $S$ is a WQO as well. ...

3

I'd say no. Consider the following example. Let $(A,\land)$ and $(B,\land)$ be two unrelated semilattices. Let $(S,\land)$ be their direct product, and put $(a,b)\le_1(a',b')$ iff $a\le a'$, $(a,b)\le_2(a',b')$ iff $b\le b'$. Then your conditions are satisfied, even though the two preorders look nothing like each other.

2

According to this reference (1), the lexicographically first topological order problem is NLOG-complete. You may want to take a more thorough look at the article to ensure that it covers the case(s) that you're interested in. In particular, based on the technical report version (pdf) of that article, it appears that they're treating the lexicographic ...

2

A trivial observation is that if $|S(x)| \le 2$ for all $x$, then this problem is solvable in polynomial time, by reduction to 2SAT. Here's how. Introduce a variable $v_{x,i}$ for each vertex $x$ and each $i$ such that $i \in S(x)$. For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, ...

2

Note that if you relax the problem by allowing $f$ to be arbitrary (not necessarily bijective), then it becomes polynomial. The algorithm proceeds similarly to topological sorting: you number the vertices one by one, maintaining the set $U$ of unnumbered vertices whose in-neighbors have been numbered. Whenever possible, you choose a vertex $x \in U$ and ...

2

I show below that the $G$-test problem is NP-hard for some simple but infinite group $G$. The finite case is still open. proof Define the following functions: $f(x) = -x$ and $g_a(x) = x + a$. Then take $G$ to be the group generated by $f$ and $g_a$ with composition as the operation. Note that the elements of $G$ are $\{f \circ g_a | a \in \mathbb{Z} \} \... 1 Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck). The main thing we have for now is a partial result on so-called crown-free lattices. To show it, for two elements$x,y$of the poset$P$, I say that$x$is covered by$y$if$x\geq y$,$x \neq y\$, and there are no elements in between ...

1

With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the case where the partial order on the elements consists of a union of chains: see Theorem 6.2. We would conjecture that the problem for general DAGs is also in NL, ...

1

Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.

Only top voted, non community-wiki answers of a minimum length are eligible