1

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?

Hans Schmuber
  • 393
  • 1
  • 7
  • 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. – Emil Jeřábek Feb 20 '24 at 14:43
  • 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). – Emil Jeřábek Feb 20 '24 at 14:50
  • 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 Feb 20 '24 at 19:57
  • 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. – Emil Jeřábek Feb 20 '24 at 20:25
  • Thank you, this is exactly that I was looking for! – Hans Schmuber Feb 21 '24 at 15:55

0 Answers0