# Tag Info

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 ...
• 9,547
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 ...
• 2,768
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 ...
• 9,547
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-...
• 37.4k

### 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 ...
• 24.8k
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)$...
• 10.8k
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 ...
• 8,903
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.
• 560

### 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 ...
• 37.4k
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 ...
• 625

### 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. ...
• 12.2k
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 ...
• 627

### 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 ...
• 2,768
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. ...
• 37.4k
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\}$ ...
• 37.4k

### 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 ...
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 ...
• 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 ...
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 ...
• 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 ...
• 563

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