P vs. BPP ★★★
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 , where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.
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.
P vs. PSPACE ★★★