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$?

Improve this question
$\endgroup$
3
  • $\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, 2018 at 7:43
  • 1
    $\begingroup$ Is $l$ a fixed number? What about $36=4*9=6*6$? $\endgroup$
    – Wei Zhan
    Feb 14, 2018 at 19:57
  • $\begingroup$ @WillardZhan gonna change definition now. Shortly, of all partitions we should choose shortest (6*6 here). $\endgroup$
    – rus9384
    Feb 14, 2018 at 20:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.