![](/files/happy5.png)
Folklore
P vs. BPP ★★★
Author(s): Folklore
Keywords: BPP; circuit complexity; pseudorandom generators
Shuffle-Exchange Conjecture ★★★
Author(s): Beneš; Folklore; Stone
Given integers , let
be the smallest integer
such that the symmetric group
on the set of all words of length
over a
-letter alphabet can be generated as
(
times), where
is the shuffle permutation defined by
, and
is the exchange group consisting of all permutations in
preserving the first
letters in the words.
![$ d(k,n) $](/files/tex/858410106f855d4731af6a7f19dd3ded70f81b08.png)
![$ d(k,n)=2n-1 $](/files/tex/b83b000fc1d6dd29fb829a03beffef104b4df30e.png)
![$ k,n\ge2 $](/files/tex/1041e1f578aec49a27fbc841578eac3503c9f753.png)
Keywords:
Shuffle-Exchange Conjecture (graph-theoretic form) ★★★
Author(s): Beneš; Folklore; Stone
Given integers , the 2-stage Shuffle-Exchange graph/network, denoted
, is the simple
-regular bipartite graph with the ordered pair
of linearly labeled parts
and
, where
, such that vertices
and
are adjacent if and only if
(see Fig.1).
Given integers , the
-stage Shuffle-Exchange graph/network, denoted
, is the proper (i.e., respecting all the orders) concatenation of
identical copies of
(see Fig.1).
Let be the smallest integer
such that the graph
is rearrangeable.
![$ r(k,n) $](/files/tex/89439aec31f70c82907b7174d89cdee92f6deba0.png)
![$ r(k,n)=2n-1 $](/files/tex/2b890eb205a3c491b93472737bc3c1b09b1fa787.png)
Keywords:
P vs. PSPACE ★★★
Author(s): Folklore
Keywords: P; PSPACE; separation; unconditional
![Syndicate content Syndicate content](/misc/feed.png)