I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one object into another?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ Interesting question. I am a bit skeptical that there is an example, since usually there is some sort of dynamic program that runs in exponential time. $\endgroup$– Tony HuynhCommented Apr 7, 2016 at 23:04
-
4$\begingroup$ This is a contrived example. but finding the permutation that maximises a hash function of that permutation is probably not going to have a subfactorial algorithm. $\endgroup$– Terry TaoCommented Apr 8, 2016 at 1:42
-
1$\begingroup$ @TerryTao That example is indeed contrived, but the idea of a one-way function shows there are problems that exist in the class I am thinking of! $\endgroup$– Bryce SandlundCommented Apr 8, 2016 at 14:58
-
2$\begingroup$ Ah, right, I should have said "one-way function" instead of "hash function"; if one hashes down to a range that is much smaller than n! then one can halt as soon as one reaches the maximum of that range, which is likely to happen in subfactorial time. But if one maps to a range much larger than n! then one can't take this shortcut. $\endgroup$– Terry TaoCommented Apr 8, 2016 at 16:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If you are also interested in problems of that type where $n = \infty$: Given a mapping $f: \mathbb{N} \rightarrow \mathbb{N}$ from the natural numbers to themselves, it is often a notoriously hard problem to decide whether there is a permutation $\sigma$ of $\mathbb{N}$ such that the conjugate $f^\sigma = \sigma^{-1} f \sigma$ maps every natural number greater than $1$ to a smaller natural number, even if the mapping $f$ can be described very easily. -- For example, if one could solve this problem for the mapping $$ T: \ \mathbb{N} \rightarrow \mathbb{N}, \ \ n \ \mapsto \ \begin{cases} n/2 & \text{if} \ n \ \text{is even}, \\ (3n+1)/2 & \text{if} \ n \ \text{is odd}, \end{cases} $$ this would tell whether the Collatz conjecture holds or not.
answered Apr 7, 2016 at 21:42
$\begingroup$
$\endgroup$
1
I think this might fit into your category, which basically is about determining if a boolean function possesses some symmetries. It is NP-complete.
answered Apr 7, 2016 at 22:30
-
5$\begingroup$ The abstract says the problem can be solved in time $2^n$, which is $o(n!)$. $\endgroup$ Commented Apr 7, 2016 at 22:53