Questions tagged [permutations]
The permutations tag has no usage guidance.
21
questions with no upvoted or accepted answers
11
votes
0answers
292 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 ...
8
votes
0answers
387 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 ...
7
votes
0answers
208 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}\...
6
votes
0answers
215 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 ...
6
votes
0answers
208 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 (...
6
votes
0answers
149 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 ...
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 ...
4
votes
0answers
78 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 ...
4
votes
0answers
89 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 $\...
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, ...
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 ...
2
votes
0answers
64 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\}^...
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 ...
asked Sep 22 '16 at 13:25
Mohammad Al-Turkistany
20.2k4 gold badges55 silver badges138 bronze badges
2
votes
0answers
132 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 ...
1
vote
0answers
38 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 ...
1
vote
0answers
57 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 ...
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 ...
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 ...
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 ...
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 ...
