1
$\begingroup$

Input: Any number $n \in \mathbb{Z}^+$ that can be represented in the form of $n = 2^a + b,\ |b|= c $. output: YES if $n$ is prime , else NO .

Now, length of binary input is $\log(a) + O(1)$ which otherwise would be order $a$. What would be the complexity of such problem? If we use AKS algorithm in straight forward way we would not get polynomial time algorithm, I think. Can we define new problems by tweaking the standard problems in P to make them harder in this way i.e. by restricting the input in certain way.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The succinct version of problems are exponentially harder (e.g. Succinct-SAT is NExpTime-complete). Yours is a restricted case of succinct version of Prime. $\endgroup$
    – Kaveh
    Commented Dec 30, 2012 at 6:14
  • $\begingroup$ Thanks, I was not aware that succinct version of problems is already well explored area. $\endgroup$
    – DurgaDatta
    Commented Dec 30, 2012 at 6:26
  • $\begingroup$ You are welcome. ps: You may want to have a look at Russell Impagliazzo's answer to the padding question. $\endgroup$
    – Kaveh
    Commented Dec 30, 2012 at 6:28
  • $\begingroup$ @Kaveh make this an answer ? $\endgroup$
    – Suresh Venkat
    Commented Jan 2, 2013 at 16:50

0

Reset to default

Your Answer

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