Questions tagged [permutations]
The permutations tag has no usage guidance.
85
questions
3
votes
1
answer
169
views
What’s the complexity of this decision problem with bit shifting?
I’ve been wondering about the computational complexity of a problem that involves bit shifting.
Let me define some notation before I present the problem.
If $\langle{b}\rangle$ is a bitstring ...
2
votes
1
answer
99
views
Shortest Common Supersequence of Permutations
For integers $k$ and $n$, let $P_{k,n}$ be the set of all size-$k$ sets of permutations of $[n]$.
The Shortest Common Supersequence for Permutations (SCSP) problem is:
given a set $S\in P_{k,n}$, ...
- 185
0
votes
0
answers
42
views
Speed networking algorithm
I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
- 101
4
votes
0
answers
250
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 20.8k
2
votes
0
answers
63
views
Partition of a set of integers into subsets where the max. of the subset-sums is minimum
Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements.
Let $\mathcal{P}$ denote the set of ...
10
votes
1
answer
432
views
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
Consider the following decision problem over a fixed alphabet $\Sigma$:
Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$
Output: does there exist a permutation $\...
- 8,896
2
votes
0
answers
43
views
Is there a name and context where function for permutation defined as f(k) = #σ({1,2,…,k})∩{1,2,…,k} appeared ? (Measure of locality)
Context: Thinking on some machine learning questions on comparing the feature importances produced by different methods - the following measure of concordance between two ordered lists seems to be ...
2
votes
0
answers
59
views
hardness of partition of permutation into a minimum number of monotone subsequences
Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
- 71
6
votes
1
answer
484
views
Number of permutations that satisfy a given set of comparisons
We are given a set of comparisons of the form z[i] < z[j] for various i and j and an ...
- 419
1
vote
1
answer
176
views
Decomposition of a permutation into increasing subsequences
Given a permutation $P$, the goal is to decompose this permutation into $k$ increasing subsequences $L_1,L_2,\ldots,L_k$, such that every element in $P$ appears exactly once in some increasing ...
- 137
4
votes
0
answers
207
views
What does width $4$ permutation branching program correspond to?
$L$ can be computed by a family of programs over $S_3$
of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of
polynomial size.
$L$ can be computed by a family ...
- 12.8k
4
votes
0
answers
94
views
Inverting Kronecker product on vectors is in P?
Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V).
Example:
Input: V={...
- 61
2
votes
0
answers
52
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 ...
- 121
0
votes
1
answer
142
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 \...
- 720
5
votes
0
answers
145
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 ...
- 101
11
votes
1
answer
319
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 ...
- 521
1
vote
0
answers
92
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 ...
- 311
4
votes
0
answers
83
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 ...
- 311
4
votes
0
answers
76
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 ...
- 596
7
votes
0
answers
249
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}\...
- 596
7
votes
1
answer
280
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''...
- 437
2
votes
0
answers
70
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,572
1
vote
1
answer
97
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 $...
- 1,572
2
votes
1
answer
168
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?
- 143
3
votes
0
answers
121
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 $\...
- 437
2
votes
1
answer
124
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 ...
- 225
8
votes
3
answers
970
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)|$ ...
- 563
9
votes
2
answers
177
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$, ...
- 1,572
2
votes
0
answers
207
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 ...
- 20.8k
6
votes
1
answer
334
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 ...
- 20.8k
11
votes
1
answer
386
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 ...
- 11.7k
5
votes
2
answers
2k
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 ...
- 1,737
4
votes
1
answer
358
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 ...
- 1,224
0
votes
1
answer
225
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 ...
- 653
3
votes
1
answer
222
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 ...
- 20.8k
16
votes
1
answer
808
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
1
answer
794
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 ...
- 8,896
1
vote
0
answers
127
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 ...
- 11
11
votes
4
answers
909
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 ...
- 242
17
votes
1
answer
1k
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 ...
- 511
4
votes
0
answers
162
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, ...
- 20.8k
13
votes
2
answers
1k
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 ...
- 133
10
votes
1
answer
797
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=...
- 13.6k
2
votes
1
answer
72
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 ...
- 531
10
votes
1
answer
342
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 ...
- 101
4
votes
0
answers
124
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,292
1
vote
1
answer
180
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-...
- 1,292
11
votes
0
answers
304
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,292
1
vote
0
answers
127
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 ...
- 1,292
8
votes
1
answer
257
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 := \...
- 1,292