<p>I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally I would like this problem to be hard, even for an EXPTIME Turing Machine.</p>
<p>As far as it currently known, this problem is not in P, but is contained in NP<span class="math-container">$\cap$</span>coNP. I'd like to know if there's a succinctly encoded version which is not contained in EXP, but is contained in NEXP<span class="math-container">$\cap$</span>coNEXP (or has some other evidence for intractability for EXPTIME TMs).</p>
<p>It's known that for any language, one can get a succinct version of the problem by choosing the bit strings corresponding to* <span class="math-container">$2^k$</span>, <span class="math-container">$k=0,1,2,\dots$</span>, but for factoring in particular, this runs the risk of these particular strings corresponding to easily factorable numbers. Is there an obvious way of encoding the factoring problem such that this the strings correspond to instances which are expected to be hard?</p>
<p>*See the answer given here: <a href="https://cstheory.stackexchange.com/questions/10529/is-there-a-succinct-representation-for-all-problems">Is there a succinct representation for all problems?</a></p>

CC BY-SA 4.0
2024-02-20T14:43:37.057Z
The standard way to define a succinct version of a given language is to take as input a Boolean circuit whose truth table (which is an exponentially long string) is passed as input to the original problem. I see no reason this shouldn't work here as well, though proving the resulting problem is not in EXP will be difficult.
Emil Jeřábek
CC BY-SA 4.0
2024-02-20T14:50:25.830Z
And actually, this is what the linked answer says. It seems you are misreading it. It is *not* using as input the binary representations of the powers $2^k$ (which are, indeed, trivial to factorize). It only says the *lengths* of the generated strings will be powers of $2$, but (1) this shouldn't matter for factoring, (2) it's trivial to circumvent (in fact, for factoring, it is already circumvented under the literal reading, as the representation allows leading $0$s).
Emil Jeřábek
CC BY-SA 4.0
2024-02-20T19:57:07.380Z
Sorry, I had meant that, and you're entirely correct. I guess the thrust of my question is, given the language formed of integers with string lengths 2^k, k=1,2,..., is there any reasonable assumptions which say these strings are not factorable in EXP?
Hans Schmuber
CC BY-SA 4.0
2024-02-20T20:25:35.210Z
*All* integers can be padded to length $2^k$ with leading zeros, so this is not a restriction at all. The real restriction is that you only consider integers describable by small circuits. In any case, it is a reasonable assumption that succinct factoring is not in EXP.
Emil Jeřábek
CC BY-SA 4.0
2024-02-21T15:55:30.410Z
Thank you, this is exactly that I was looking for!
Hans Schmuber
<cc.complexity-theory><factoring><succinct>
Is there a succinct representation of factoring which remains computationally intractable?
Hans Schmuber
# Is there a succinct representation of factoring which remains computationally intractable?

(Asked by: username_0 on 2024-02-20)

I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally I would like this problem to be hard, even for an EXPTIME Turing Machine.

As far as it currently known, this problem is not in P, but is contained in NP$\cap$coNP. I'd like to know if there's a succinctly encoded version which is not contained in EXP, but is contained in NEXP$\cap$coNEXP (or has some other evidence for intractability for EXPTIME TMs).

It's known that for any language, one can get a succinct version of the problem by choosing the bit strings corresponding to\* $2^k$, $k=0,1,2,\dots$, but for factoring in particular, this runs the risk of these particular strings corresponding to easily factorable numbers. Is there an obvious way of encoding the factoring problem such that this the strings correspond to instances which are expected to be hard?

\*See the answer given here: [Is there a succinct representation for all problems?](https://cstheory.stackexchange.com/questions/10529/is-there-a-succinct-representation-for-all-problems)

**Tags:** cc.complexity-theory, factoring, succinct
> **Comments:**
> **username_1**: The standard way to define a succinct version of a given language is to take as input a Boolean circuit whose truth table (which is an exponentially long string) is passed as input to the original problem. I see no reason this shouldn't work here as well, though proving the resulting problem is not in EXP will be difficult.  
> **username_1**: And actually, this is what the linked answer says. It seems you are misreading it. It is *not* using as input the binary representations of the powers $2^k$ (which are, indeed, trivial to factorize). It only says the *lengths* of the generated strings will be powers of $2$, but (1) this shouldn't matter for factoring, (2) it's trivial to circumvent (in fact, for factoring, it is already circumvented under the literal reading, as the representation allows leading $0$s).  
> **username_0**: Sorry, I had meant that, and you're entirely correct. I guess the thrust of my question is, given the language formed of integers with string lengths 2^k, k=1,2,..., is there any reasonable assumptions which say these strings are not factorable in EXP?  
> **username_1**: *All* integers can be padded to length $2^k$ with leading zeros, so this is not a restriction at all. The real restriction is that you only consider integers describable by small circuits. In any case, it is a reasonable assumption that succinct factoring is not in EXP.  
> **username_0**: Thank you, this is exactly that I was looking for!  

---

## 0 answers

