1
$\begingroup$

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

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

2 Answers 2

1
$\begingroup$

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$.

There is no way to do this that is any better than trying different permutations at random until you hit on the right one.

$\endgroup$
1
  • $\begingroup$ Yes, this fits in the category of a permutation search problem with no o(n!) solution. I am interested, however, in natural problems that one might actually want to solve. Graph isomorphism, hypergraph isomorphism, permutation group conjugacy equivalence, and problems of this nature are interesting, however admit reasonably efficient backtrack searches. $\endgroup$ Apr 20, 2016 at 1:36
0
$\begingroup$

The Quadratic Assignment Problem is another example of notoriously hard Problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.