Questions tagged [permutations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
70 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 ...
Matt Samuel's user avatar
11 votes
2 answers
263 views

Is there a simple characterization of regular languages closed under circular shifts?

A language $L$ is closed under circular shifts if, for every word $w = a_1 ... a_n$ and circular shift $w' = a_i ... a_n a_1 ... a_{i-1}$ of $w$, then $w \in L$ iff $w' \in L$. It is equivalent to ...
a3nm's user avatar
  • 9,232
2 votes
0 answers
30 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 ...
Pur2all's user avatar
  • 21
3 votes
1 answer
183 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 ...
Sophie Weigle's user avatar
2 votes
1 answer
107 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}$, ...
igel's user avatar
  • 185
0 votes
0 answers
43 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 ...
Helen Grey's user avatar
4 votes
0 answers
278 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 ...
Mohammad Al-Turkistany's user avatar
2 votes
0 answers
65 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 ...
Code-searcher's user avatar
11 votes
1 answer
446 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 $\...
a3nm's user avatar
  • 9,232
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 ...
Alexander Chervov's user avatar
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 ...
steven kelk's user avatar
6 votes
1 answer
495 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 ...
Arthur B's user avatar
  • 429
1 vote
1 answer
184 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 ...
Vk1's user avatar
  • 137
4 votes
0 answers
209 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 ...
Turbo's user avatar
  • 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={...
luciano's user avatar
  • 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 ...
Timothy's user avatar
  • 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 \...
orlp's user avatar
  • 835
5 votes
0 answers
150 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 ...
user340082710's user avatar
11 votes
1 answer
325 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 ...
Ville Salo's user avatar
1 vote
0 answers
97 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 ...
RTK's user avatar
  • 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 ...
RTK's user avatar
  • 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 ...
Joseph Van Name's user avatar
7 votes
0 answers
250 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}\...
Joseph Van Name's user avatar
7 votes
1 answer
283 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''...
Zihan Tan's user avatar
  • 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\}^...
Samuel Schlesinger's user avatar
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 $...
Samuel Schlesinger's user avatar
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?
Oleksandr  Kulkov's user avatar
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 $\...
Zihan Tan's user avatar
  • 437
2 votes
1 answer
125 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 ...
Max Hopkins's user avatar
8 votes
3 answers
985 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)|$ ...
maxdan94's user avatar
  • 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$, ...
Samuel Schlesinger's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
6 votes
1 answer
335 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 ...
Mohammad Al-Turkistany's user avatar
11 votes
1 answer
396 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 ...
D.W.'s user avatar
  • 12k
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 ...
Charles's user avatar
  • 1,735
4 votes
1 answer
362 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 ...
Lior Eldar's user avatar
  • 1,224
0 votes
1 answer
227 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 ...
Omar Shehab's user avatar
3 votes
1 answer
226 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 ...
Mohammad Al-Turkistany's user avatar
17 votes
1 answer
820 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 ...
Mateus de Oliveira Oliveira's user avatar
25 votes
1 answer
795 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 ...
a3nm's user avatar
  • 9,232
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 ...
user32856's user avatar
11 votes
4 answers
916 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 ...
Jayen's user avatar
  • 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 ...
Vsevolod Oparin's user avatar
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, ...
Mohammad Al-Turkistany's user avatar
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 ...
user27313's user avatar
  • 133
10 votes
1 answer
816 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=...
Scott Aaronson's user avatar
2 votes
1 answer
73 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 ...
kjo's user avatar
  • 531
10 votes
1 answer
345 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 ...
Charles Mosley's user avatar
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 ...
NisaiVloot's user avatar
  • 1,292
1 vote
1 answer
181 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-...
NisaiVloot's user avatar
  • 1,292