# Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (discussed in the comments).

I am now asking for a more natural permutation search problem with no efficient solution in practice.

An example where this is not the case is the graph isomorphism problem, which has no known polynomial time solution, but backtrack search can perform very well on all known classes of graphs [1].

Therefore, I am wondering if there are other permutation search problems that are either considered intractable in practice, or whose backtracking heuristics have known classes of problems in which they perform very poorly.

[1]: Practical Graph Isomorphism II, McKay, http://arxiv.org/pdf/1301.1493v1.pdf

• Actually, Graph Isomorphism has a quasi-polynomial time algorithm, according to Babai. Not quite polynomial, but much smaller than $n!$. Apr 20 '16 at 0:02

Here's the hardest of all permutation search problems. Alice chooses a particular permutation $p_A$ of $[1,\ldots, n]$. You have access only to a black-box function that, for a given permutation $p$, will tell you whether or not your permutation is $p_A$. Find $p_A$.