3
$\begingroup$

Some terminology at first:

  1. Multiplicative 2-partition for number $N$ - a pair of numbers $\{A, B\}$ such that $AB=N$.

  2. Minimal multiplicative 2-partition length (denoted $l$) - minimal total number of bits needed to encode multiplicative one of 2-partitions.

Example:

Let $N = 36$. Then possible multiplicative 2-partitions are $\{2, 18\}, \{3, 12\}, \{4, 9\}, \{6, 6\}$. Their lengths are 7=2+5, 6=2+4, 7=3+4, 6=3+3 respectively. Minimal length here is 6, so $l=6$.

The input: non-prime $n$-bit number $N$.

The problem: find out if $n = l$.

YES-instance:

$N$ = 49, since $n$ = 6 and each multiplier takes 3 bits.

NO-instance:

$N$ = 25, since $n$ = 5 and each multiplier takes 3 bits.

The question: what is the complexity for this problem? It's trivial that it's not harder than factoring and I guess it's $PL$-hard. But is it even known to be in $P$?

$\endgroup$
  • $\begingroup$ Sounds likely to be approximately as hard as factoring. If $N=PQ$ where $P,Q$ are two primes, factoring $N$ is hard, and it's probably hard to distinguish between the case where the smaller prime factor has $n/2$ bits vs where it has $n/2-1$ bits bits (say). $\endgroup$ – D.W. Feb 14 '18 at 7:43
  • 1
    $\begingroup$ Is $l$ a fixed number? What about $36=4*9=6*6$? $\endgroup$ – Willard Zhan Feb 14 '18 at 19:57
  • $\begingroup$ @WillardZhan gonna change definition now. Shortly, of all partitions we should choose shortest (6*6 here). $\endgroup$ – rus9384 Feb 14 '18 at 20:05

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.