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

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

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Bryce Sandlund
    Commented Apr 20, 2016 at 1:36
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .