Given as input:

  • an ordered list of distinct prime numbers $A = ( p_1,p_2,...,p_n )$,
  • a set of triples $B = \{ (a_1, b_1, c_1 ), (a_1, b_1, c_1 ), ...., (a_m, b_m, c_m ) \}$, where $a_i, b_i, c_i \in A$ represent the factorization of the number: $$x = a_1^{b_1 c_1} \cdot a_2^{b_2 c_2} \cdot ... \cdot a_m^{b_m c_m}$$

  • and an integer $K$

Can we calculate in polynomial time if there exists a permutation $\pi$ of $[1..n]$ such that

$$\bar x = \bar a_1^{\bar b_1 \bar c_1} \cdot \bar a_2^{\bar b_2 \bar c_2} \cdot ... \cdot \bar a_m^{\bar b_m \bar c_m}$$

is less than $K$ ?

(where $\bar a_{i}, \bar b_{i}, \bar c_{i}$ are simply the permutation of the corresponding prime,
for example if $a_i = p_j$ then $\bar {a_i} = p_{\pi(j)}$)

Very informally:

Can we shuffle the primes of $x$ and make it less than $K$ ?

Does the problem become easier if $B$ is a set of pairs $\{a_i,b_i\}$ that represents the number: $$x' = a_1^{b_1} \cdot ... \cdot a_m^{b_m}$$

  • $\begingroup$ Polynomial in what? $\endgroup$ – user9072 May 16 '15 at 21:15
  • 1
    $\begingroup$ @quid: in the size of the input, i.e. the length of $A$ and $B$ as a list of binary strings and length of $K$ (a binary string) $\endgroup$ – Marzio De Biasi May 16 '15 at 21:18
  • 1
    $\begingroup$ Premutation is a nice word but you might have meant permutation. $\endgroup$ – domotorp May 16 '15 at 21:29
  • $\begingroup$ @domotorp: "My English is not very good looking" [cit.] ... that word could be used for a radical new theory ... the "theory of premutations" :-) :-). $\endgroup$ – Marzio De Biasi May 16 '15 at 21:34

Your Answer

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

Browse other questions tagged or ask your own question.