17
$\begingroup$

I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$:

If $A$ is an oracle that solves integer factorization, what is the power of $P^A$?

I think it makes RSA-based public-key cryptography insecure ... but apart from this, are there other remarkable results?

$\endgroup$
  • 3
    $\begingroup$ @Vor that part P(Q is trivial)=1 is a joke, isn't it? $\endgroup$ – Pratik Deoghare Feb 7 '11 at 15:35
  • $\begingroup$ This question suggests a related and (perhaps) more natural question: if R is an oracle that returns f_(_M,n) as the maximal runtime of a polynomial-time Turing machine M over all inputs of length n, what is the power of P^R? $\endgroup$ – John Sidles Feb 7 '11 at 17:10
  • 2
    $\begingroup$ @Vor: Isn't this the same as asking "Which problems can be polynomial-time Turing reduces to integer factorization?" Or did you intend to ask something else? $\endgroup$ – Joshua Grochow Feb 8 '11 at 4:54
  • $\begingroup$ I'm a newbie, so my question is almost a curiosity. All started from a simple thought: out "in the real world" I see many NP-complete problems (a postman trying to reserve his strength, a family that is moving and want to fit its furniture in a truck, ... :-))). But I don't see "factoring problems" ... although they MAY be simpler (between P and NPC). ... perhaps reality hates multiplications :-D :-D $\endgroup$ – Marzio De Biasi Feb 8 '11 at 8:07
  • 1
    $\begingroup$ See also Consequences of Factoring being in P? $\endgroup$ – Jukka Suomela Feb 24 '11 at 9:53
11
$\begingroup$

I don't have an answer to you question, but I know that a similar notion has very recently been studied, under the name of "angel-based security."

The first paper studying this concept is Prabhakaran & Sahai (STOC '04). In particular, they wrote in the abstract:

[... we give the] adversary access to some super-polynomial computational power.

Another important paper which discusses this notion is that of Canetti, Lin, & Pass (FOCS 2010). I watched some parts of their conference presentation (on techtalks), and if I recall correctly, they start with an example similar to what you mentioned in the question.

$\endgroup$
13
$\begingroup$

Obviously any decision problem that can be reduced to factoring can be solved with a factoring oracle. But since we're given the ability to make multiple queries, I tried to think of a non-trivial problem for which one would want to make multiple queries.

The problem of computing the Euler totient function seems like such a problem. I don't know how to solve the decision version of this problem by a Karp-reduction to the decision version of factoring. But with Turing reductions, it's easy to reduce this to factoring.

$\endgroup$
  • 3
    $\begingroup$ Here's a related post in MO concerning the complexity of computing totient function. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 8 '11 at 5:04
  • $\begingroup$ Small addition: there are also polynomial time reductions in the other direction, computing Euler's Totient function -> Factoring. I have not checked whether the known reductions work for the decision version of these problems though. Still, being able to compute the Totient function (or even a fixed multiple of it) gives you the ability to factorize. Shoup's book dedicates a chapter to this. $\endgroup$ – Juan Bermejo Vega Jul 15 '14 at 9:58
9
$\begingroup$

Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap coNP} = NP}$. This implies in particular that $$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$$ We may make similar remarks for $\mathsf{coNP}$ and $\mathsf{BQP}$, to show that at least on a coarse-grained level, $\mathsf P^{\textrm{FACTORING}}$ has the same complexity bounds as the problem $\textrm{FACTORING}$ itself, which is to say $$ \mathsf{P^{\textrm{FACTORING}} \subseteq NP \cap coNP \cap BQP}.$$

$\endgroup$
  • $\begingroup$ Thanks for the new answer. BTW, are you aware of papers/results about reducibility among problems in $NP \cap coNP$? $\endgroup$ – Marzio De Biasi Mar 31 '14 at 16:09
  • 3
    $\begingroup$ It's even in $\mathsf{UP} \cap \mathsf{coUP}$ (the same reasoning as in your answer holds). $\endgroup$ – Joshua Grochow Mar 31 '14 at 22:51
6
$\begingroup$

Since factorization is in NP, you can at least say that $P^A\subseteq \Delta_2^P$.

$\endgroup$
5
$\begingroup$

Well, as others noted factorization is in $\mbox{FNP}$, so we have $P \subseteq P^A \subseteq \Delta_2^p$ (i.e. $P^{NP}$). However, the decision version of factoring is also in $\mbox{BQP}$, so in fact we can do slightly better and get $P \subseteq P^A \subseteq P^{NP \cap BQP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.