Questions tagged [permutations]
The permutations tag has no usage guidance.
73
questions
1
vote
0answers
32 views
Dynamic permutation cycle data
Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?
sameCycle($\pi,x,y$): determines ...
0
votes
1answer
78 views
Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?
$\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity
$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$
of some string of symbols $x \in \...
4
votes
0answers
128 views
Characterizing the ANF of Single-Cycle Boolean Permutations
Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We ...
11
votes
1answer
270 views
Reversible polynomial circuit iff polynomial reversible circuit?
My question is about efficiently computable bijective functions. Informally I'm interested in:
If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective ...
1
vote
0answers
56 views
How to efficiently verify if a semantic symmetry of a CNF formula is valid?
It is easy to verify that a syntactic symmetry of a CNF formula is correct.
Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is ...
4
votes
0answers
76 views
Finding a largest symmetrical subset of a k-CNF propositional formula
I have a k-CNF propositional formula $F$ which do not admit any global symmetry i.e. there is no permutation $\sigma$ of its variables such that $\sigma(F) = F$ . I'm interested in finding the largest ...
4
votes
0answers
66 views
Can an efficiently computable non-one way permutation be written as the composition of polynomially many easy to compute involutions?
Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ where if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijection where both $f$ and $f^{-1}$ are computable by circuits with at ...
7
votes
0answers
202 views
Can every efficiently computable permutation be written as the composition of two efficiently computable involutions?
It is well-known that every permutation can be written as the composition of two involutions.
Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ such that if $f:\{0,1\}^{n}\...
7
votes
1answer
266 views
Distinguishability a set of permutations
Given integers $d<n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is ``distinguishable''...
2
votes
0answers
63 views
Can we compute encodings of binary strings under arbitrary permutation groups?
Given a permutation group $G \leq S_n$, can you construct non-uniformly a circuit computing a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log|\{0, 1\}^n/G_n|)}$ with size $O_n(\frac{|\{0, 1\}^...
1
vote
1answer
76 views
What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?
If we have some string $x$ and a permutation $g$ which preserves the bits of $x$, we can store the value of $x$ on each of its $g$-orbits as well as $g$ instead of storing $x$ and we can reconstruct $...
2
votes
1answer
144 views
Computing size of permutation group from generators
You're given $k$ permutations $a_1,\dots,a_k$. Consider closure of this set under the composition operation. What are most efficient and simple algorithms to calculate the size of this closure?
3
votes
0answers
88 views
Finding the longest sub-permutation with bounded inversion number
Given a permutation $\sigma\in S_n$ and a positive integer $k$, find the largest integer $0\le m\le n$ such that there exist a subset $I\subseteq [n], |I|=m$, satisfying that the restriction of $\...
1
vote
0answers
72 views
Function which detects rotation of bit string
Consider a function $F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$ with the property that if $y \in \mathbb{F}_2^d$ is a rotation of $x \in \mathbb{F}_2^d$, i.e. $y$ is $x$ permuted by an ...
7
votes
2answers
613 views
Is this vertex ordering optimization NP-Hard?
Could you help me to prove that the following problem is NP-hard?
Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
9
votes
2answers
165 views
Complexity of Computing Lexicographically Minimal Element of Orbit
Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, ...
2
votes
0answers
200 views
Candidates for combinatorial one-way permutation
It is known that (worst-case) one-way permutations exist if and only if $P\ne UP \cap coUP$. Almost all candidates that I know are based on hard number theortic problems. I came across a combinatorial ...
6
votes
0answers
213 views
Proving P-Isomorphism between two languges
The famous Isomorphism Conjecture states that all NP-complete problems are isomorphic via polynomial-time computable and invertible bijections (reductions). Padability is the only property that I know ...
10
votes
1answer
301 views
Evaluating symmetric polynomials
Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$. For convenience, we ...
5
votes
2answers
1k views
Matrix permanent is 0
Valiant's theorem says that computing the permanent of an $n\times n$ matrix is #P-hard. Is the problem of determining if a permanent is 0 any easier? This arises in the context of sequence A006063 in ...
4
votes
1answer
259 views
The complexity of decomposing a bi-stochastic matrix
A bistochastic matrix $A$ is a matrix with positive entries in which
each row/column sums to $1$.
By the Birkhoff von-Neumann theorem $A$ is a convex combination of
permutation matrices.
Further, by ...
0
votes
1answer
192 views
Graph isomorphism problem with invertible adjacency matrices
This question is supplementary to the question asked here.
One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows.
Given a ...
3
votes
1answer
203 views
How hard is recognizing a permutation that is a square for the shift product?
This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
15
votes
1answer
755 views
Permutations with forbidden subsequences
Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition.
Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a ...
25
votes
1answer
757 views
Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences
For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
1
vote
0answers
120 views
Minimize L2 norm by circular permutation
Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that
$\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$?
Of course one can take all the ...
12
votes
4answers
569 views
Reordering data (set of strings) to optimize for compression?
Are there any algorithms for reordering data to optimize for compression? I understand this is specific to the data and the compression algorithm, but is there a word for this topic? Where can I ...
16
votes
1answer
817 views
Computing parity of a permutation in a streaming-fashion way
I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
4
votes
0answers
148 views
Recognition problem of cycle permutation graphs
A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
13
votes
2answers
655 views
Complexity of permutation related problems
Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there ...
10
votes
1answer
686 views
Probability of generating a desired permutation by random swaps
I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=...
2
votes
1answer
67 views
Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size
I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2. (FWIW, the ...
10
votes
1answer
313 views
Recent progress in permutation groups algorithms?
I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are ...
4
votes
0answers
104 views
The rank-polynomial of a graded poset
Let $P$ be a graded poset with rank function $r$. We may then define its rank-polynomial as:
$R_P(q) = \sum_{x \in P} q^{r(x)}$.
This definition can be applied to several interesting posets, for ...
1
vote
1answer
173 views
More questions about permutations
I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically.
the skew-...
11
votes
0answers
291 views
Generalizations of the determinant/permanent problem?
A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with ...
1
vote
0answers
123 views
Some algorithmic questions on permutations
I'm interested in the possibility of fast algorithms for the following two problems on permutations.
1)
Given a permutation $\pi$ and an integer $k$, compute a pair $(\mathcal{C},\mathcal{A})$ where ...
8
votes
1answer
227 views
Hierarchical sorting strategies for pattern-avoiding permutations?
For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \...
10
votes
1answer
128 views
Encoding sets of permutations with a generating set and a set of excluded elements
Polynomial-time algorithms are known for finding generating sets of permutation groups, which is interesting since we can then represent those groups succinctly without giving up on polynomial-time ...
21
votes
2answers
978 views
$NP$-completeness of recognizing the difference of two permutations
Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...
8
votes
0answers
386 views
Permutation optimization problem
Here is the problem as posed by Jerrum:
"The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target ...
4
votes
1answer
150 views
Compatible partial permutations
Please, correct my terminology as I am not a combinatorician
(I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem.
Let $P_k$ be ...
0
votes
0answers
111 views
“Partial” invert a one-way permutation
First of all, to my best understanding, traditionally, if $f$ is a one-way function that maps a length $l$ bit string to another length $l$ bit string (i.e., $f:\{0,1\}^l\rightarrow\{0,1\}^l$), then ...
2
votes
1answer
109 views
Effect of constraints Density on the hardness of Betweness problem
Betweeness problem is well known NP-complete permutation problem. Given a family $M$ of triples $(a_i, a_j, a_k)$, the problem is to decide whether a permutation $\Phi$ of elements $a_1, a_2, ..., a_n$...
-1
votes
1answer
49 views
Algorithm for calculating substitution combination with ordering
I need to calculate the combinations of elements with a substitution element.
For example for elements [A,B] if the substitution is X the results should be ...
12
votes
1answer
2k views
Efficient algorithm for existence of permutation with differences sequence?
This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations.
A differences sequence $a_1, ...
3
votes
2answers
496 views
Finding the identity with permutation chains
I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$.
How hard is to find a sequence $...
29
votes
2answers
2k views
Can you identify the sum of two permutations in polynomial time?
There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question:
Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
-3
votes
1answer
275 views
the product of a matrix and a permutation matrix [closed]
Can a permutation matrix (P) be used to change the rank of another matrix (M)?
Is there any literature to this effect, or to the contrary?
I've tried a few small examples and the resulting matrix (M2)...
3
votes
2answers
171 views
Sort with random deviations
I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a ...
