Questions tagged [permutations]
The permutations tag has no usage guidance.
30
questions with no upvoted or accepted answers
11
votes
0
answers
307
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
8
votes
0
answers
410
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 ...
- 2,359
7
votes
0
answers
251
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
6
votes
0
answers
221
views
Lowerbounds for in-situ permutation
What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (...
- 161
6
votes
0
answers
153
views
Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range
I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
- 299
5
votes
0
answers
151
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
4
votes
0
answers
284
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.9k
4
votes
0
answers
221
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.9k
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
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
77
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
4
votes
0
answers
164
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.9k
4
votes
0
answers
125
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
3
votes
0
answers
122
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
0
answers
31
views
Impossibility of uniform generation in random world
I specify that this is a cross-post from crypto.stackexchange but I didn't get satisfactory answers.
I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich ...
- 21
2
votes
0
answers
67
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 ...
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
70
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
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
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
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.9k
2
votes
0
answers
163
views
Complexity of the standardization
Let $(A, \leq)$ be a totally ordered alphabet.
The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an ...
- 131
1
vote
0
answers
35
views
Unclear relation in the number of permutations consistent with Hasse diagrams
I have been reading the paper 'Time Space Tradeoff for Sorting on Non-Oblivious Machines' by Borodin et al. (Link). Lemma 1 in that paper gives a relation between the number of permutations consistent ...
- 111
1
vote
0
answers
98
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
1
vote
0
answers
128
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
1
vote
0
answers
128
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
0
votes
0
answers
52
views
Shortest sequence that contains a given list of sequences as subsequences
Given an alphabet with $n$ characters, and a list $L$ of sequences can we approximately find the shortest sequence that contains all sequences of $L$ as subsequences?
Very similar to the question ...
- 228
0
votes
0
answers
75
views
Complexity of an algorithm involving permutations
I'm looking to figure out the computational complexity of an algorithm in an application I've written. The application computes the answer to a problem that is $\#P$-hard, and the algorithm I'm asking ...
- 111
0
votes
0
answers
46
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
0
votes
0
answers
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 ...
- 1