# Tag Info

Accepted

### Matrix permanent is 0

Expanding my comment: Computing the permanent of a matrix is #P-hard (Valiant 1979) even if the matrix entries are all either 0 or 1. We can interpret a matrix $M \in \{0,1\}^{n \times n}$ as a ...
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 ...

### Choosing random permutations in "strict" polynomial time

If the only randomness you can obtain is sampling from a set of polynomial size, you are not going to be able to get two random permutations, because the probability of any particular pair of random ...

### Evaluating symmetric polynomials

The question seems quite open ended. Or perhaps you wish to have a precise characterization of the time-complexity of any possible symmetric polynomial over finite fields? In any case, at least to my ...
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 ...
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 ...
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-...

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

### Matrix permanent is 0

If it suffices to know the parity of the permanent, you can compute it in polynomial time by computing the determinant of the matrix over the field of size 2.
Accepted

### The complexity of decomposing a bi-stochastic matrix

Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using $O(\max\{n^{d+2},n^4\})$ operations over the reals for ...
Accepted

### Graph isomorphism problem with invertible adjacency matrices

Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).
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)$...
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.

### 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 ...
Accepted

### How hard is recognizing a permutation that is a square for the shift product?

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix} \right)$$ be the shift permutation. Then ...
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 ...

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

### 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 ...
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. ...
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\}$ ...
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 ...
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 ...

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