Skip to main content
12 votes
Accepted

Number of permutations that satisfy a given set of comparisons

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has. This ...
a3nm's user avatar
  • 9,547
10 votes
Accepted

Is this vertex ordering optimization NP-Hard?

Consider your problem restricted to 3-regular graphs. Consider some ordering of the vertices. Define a split vertex to be a vertex $v$ such that both $succ(v)$ and $pred(v)$ are non-empty and define a ...
Mikhail Rudoy's user avatar
9 votes
Accepted

Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

The problem is NP-hard already for $\Sigma = \{a, b\}$. (Of course, it is in PTIME if $|\Sigma| = 1$.) The reduction is from distinct-input 3-partition which is strongly NP-hard, i.e., intractable ...
a3nm's user avatar
  • 9,547
7 votes
Accepted

Computing size of permutation group from generators

The most efficient (and also simplest) algorithms for this are based on the notion of a strong generating set, introduced by Sims. Strong generating sets can be computed efficiently using the Schreier-...
Joshua Grochow's user avatar
6 votes

Decomposition of a permutation into increasing subsequences

You seem to be assuming that an ideal decomposition exists for all permutations. It does not. Consider the permutation 6 2 4 8 10 1 3 7 9 5. The maximum length increasing subsequence is 4. If you take ...
Peter Shor 's user avatar
6 votes
Accepted

Distinguishability a set of permutations

Here are loose lower and upper bounds. Fix $d \le n$ as in the post. Let $k^*$ denote the largest possible value of $k$ meeting the conditions in the post. We show that $k^* = \exp(\Theta(d\log d)$...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

Is there a simple characterization of regular languages closed under circular shifts?

We can propose an automaton model characterizing regular circular languages: a C-automaton is an NFA where all states are initial. A run must see an accepting state somewhere, and must start and end ...
Denis's user avatar
  • 8,903
5 votes
Accepted

Complexity of Computing Lexicographically Minimal Element of Orbit

This problem is $FP^{NP}$-complete, as shown here. It means that the lexicographical leader of the orbit is built in deterministic polynomial time with access to a $NP$-oracle.
Boson's user avatar
  • 560
5 votes

Complexity of Computing Lexicographically Minimal Element of Orbit

This problem is NP-hard. Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world ...
Joshua Grochow's user avatar
4 votes
Accepted

Shortest Common Supersequence of Permutations

There should exist some absolute constant $C$ such that, the following lower bound holds: $$q_k(n) \ge kn-(C+o(1))k^2 \sqrt{n}, $$ which is much stronger than your conjecture. The idea is this: If you ...
Zach Hunter's user avatar
3 votes

What’s the complexity of this decision problem with bit shifting?

If I had to guess, I'd guess that the problem is hard, but I don't have a rigorous proof. I share below some musings on your problem, even though they don't lead to a clear answer to your question. ...
D.W.'s user avatar
  • 12.2k
3 votes
Accepted

Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set. Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then ...
Tim's user avatar
  • 627
3 votes

Deciding whether an NC${}^0_3$ circuit computes a permutation or not

This problem with $k=3$ is coNP-hard (and therefore coNP-complete). To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a ...
Mikhail Rudoy's user avatar
2 votes
Accepted

Proving P-Isomorphism between two languges

While I don't know other general properties (similar to paddability) that imply p-isomorphism, I suppose there is another way that is perhaps more "direct and natural" in the way asked for. ...
Joshua Grochow's user avatar
2 votes
Accepted

What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ ...
Joshua Grochow's user avatar
2 votes

Is there a simple characterization of regular languages closed under circular shifts?

Just an extended note trying to recover my previous (wrong) answer. A language $L$ is closed under cyclic shifts if and only if $aw \in L \Leftrightarrow wa \in L\;$ ($a \in \Sigma$) indeed after ...
Marzio De Biasi's user avatar
1 vote

How well can shortest common supersequence over small alphabet size be approximated?

Does this remain true if $n$ is bounded? No. When $n=O(1)$, there is a constant-factor approximation algorithm. See Lemma 1 below. Does this remain true if $n$ is sublinear in $|L|$? Yes. For ...
Neal Young's user avatar
  • 10.8k
1 vote

Reversible polynomial circuit iff polynomial reversible circuit?

Let $f:2^{m}\rightarrow 2^{n}$ be a function. Then define a bijection $L_{f}:2^{m}\times 2^{n}\rightarrow 2^{m}\times 2^{n}$ by letting $L_{f}(x,y)=(x,f(x)\oplus y)$. Then if $L_{f}$ has reversible ...
Joseph Van Name's user avatar
1 vote
Accepted

Function which detects rotation of bit string

This is an old but interesting question. Edit: As suggested by Emil Jerabek, $d\geq 6$ is also needed. I will interpret it by assuming $n$ should be $d$ and demonstrate that it can be solved by using ...
kodlu's user avatar
  • 2,070
1 vote

Is this vertex ordering optimization NP-Hard?

The proof here also shows NP-hardness of the problem. It shows NP-hardness of the less constrained problem where we look for an orientation of the edges instead of an ordering of the nodes (that is ...
maxdan94's user avatar
  • 563

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