12
$\begingroup$

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?

$\endgroup$
  • 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 Huynh Apr 7 '16 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 Tao Apr 8 '16 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 Sandlund Apr 8 '16 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 Tao Apr 8 '16 at 16:24
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I think this might fit into your category, which basically is about determining if a boolean function possesses some symmetries. It is NP-complete.

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ The abstract says the problem can be solved in time $2^n$, which is $o(n!)$. $\endgroup$ – Tony Huynh Apr 7 '16 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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