TIFR CSE 2011 | Part B | Question: 37

Question

Given an integer $n\geq 3$, consider the problem of determining if there exist integers $a,b\geq 2$ such that $n=a^{b}$. Call this the forward problem. The reverse problem is: given $a$ and $b$, compute $a^{b}$ (mod b). Note that the input length for the forward problem is $\lfloor\log n\rfloor + 1$, while the input length for the reverse problem is $\lfloor\log a\rfloor + \lfloor\log b\rfloor + 2$. Which of the following statements is TRUE?

• A. Both the forward and reverse problems can be solved in time polynomial in the lengths of their respective inputs.
• B. The forward problem can be solved in polynomial time, however the reverse problem is $NP$-hard.
• C. The reverse problem can be solved in polynomial time, however the forward problem is $NP$-hard.
• D. Both the forward and reverse problem are $NP$-hard.
• E. None of the above.

Comments

Just additional information. If you are checking this question then check Modular logarithm problem also. Modular logarithm problem is hard Problem.

Q ->How hard it is  ?

Ans.->  https://cs.stackexchange.com/questions/2658/how-hard-is-finding-the-discrete-logarithm

---

okay, this problem (forward problem) will be same as subset-sum problem if we remove input constraints, isn't it ?

hence this problem also became NPC, if we remove the input constraints log N+1 ? 

Correct me if i'm wrong !

Answer 1

The reverse problem can be solved in polynomial time as $a^b$ requires at most $\log b$ recursive calls using the approach given below:

pow(int a, int b)
{
    if(b%2)
        return a* pow(a*a, b/2);
    else
        return pow(a*a, b/2);
}

Now, the forward problem is also solvable in polynomial time. We need to check for all the roots of $n$  (from $\sqrt n$ till $n^{\frac{1}{\log n}}$) whether it is an integer . But each of these check can be done in $\log n$ time using a binary search on the set of integers from 2..$n$ and so, the overall complexity will be $(\log n)^2$ which is polynomial in $\log n$ ($\log n$ is the size of input). So, (a) must be the answer. 
 

Comments

what algorithm is this? why two cases, sorry i that i ask explanation for each and everything.

---

Very Good Problem and very good answer. :)

---

@gatecse 

can i do like this ?  

forward :

sort the input in polynomial time. 

place left end right end marker, check if less then i++ else j-- . ?

reverse :

it is just an exponentiation problem in polynomial time and "mod" is sequence of some arithmetic operations hence overall polynomial time.

?