17
votes
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 ...
- 2,803
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 ...
- 8,896
10
votes
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 ...
- 24.3k
10
votes
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 ...
- 1,899
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 ...
- 2,758
8
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 ...
- 8,896
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-...
- 36.9k
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
...
- 24.3k
6
votes
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.
- 962
6
votes
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 ...
- 8,821
6
votes
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).
- 1,897
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)$...
- 9,595
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.
- 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 ...
- 36.9k
4
votes
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 ...
- 1,235
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 ...
- 603
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.
...
- 11.7k
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 ...
- 617
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 ...
- 2,758
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. ...
- 36.9k
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\}$ ...
- 36.9k
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 ...
- 596
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