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

<p>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 <em>AKS algorithm</em>  in straight forward way we would not get polynomial time algorithm, I think. Can we define new problems by tweaking the standard problems in  <strong>P</strong> to make them harder in this way i.e. by restricting the input in certain way.</p>

CC BY-SA 3.0
2012-12-30T06:14:05.023Z
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.
Kaveh
CC BY-SA 3.0
2012-12-30T06:26:56.767Z
Thanks, I was not aware that succinct version of problems is already well explored area.
DurgaDatta
CC BY-SA 3.0
2012-12-30T06:28:58.133Z
You are welcome. ps: You may want to have a look at [Russell Impagliazzo's answer to the padding question](http://cstheory.stackexchange.com/a/2453/186).
Kaveh
CC BY-SA 3.0
2013-01-02T16:50:31.660Z
@Kaveh make this an answer ?
Suresh Venkat
<cc.complexity-theory><ds.algorithms><time-complexity><nt.number-theory>
Computational Complexity of RESTRICTED primality testing
DurgaDatta
# Computational Complexity of RESTRICTED primality testing

(Asked by: username_0 on 2012-12-30)

*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.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, nt.number-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks, I was not aware that succinct version of problems is already well explored area.  
> **username_1**: You are welcome. ps: You may want to have a look at [Russell Impagliazzo's answer to the padding question](http://cstheory.stackexchange.com/a/2453/186).  
> **username_2**: @username_1 make this an answer ?  

---

## 0 answers

