16
$\begingroup$

Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.

Ladner's theorem tells us that if $\mathsf{NP}\neq\mathsf{P}$ then there is an infinite hierarchy of $\mathsf{NPI}$ problems, i.e. there are $\mathsf{NPI}$ problems which are harder than other $\mathsf{NPI}$ problems.

I am looking for candidates of such problems, i.e. I am interested in pairs of problems
- $A,B \in \mathsf{NP}$,
- $A$ and $B$ are conjectured to be $\mathsf{NPI}$,
- $A$ is known to reduce to $B$,
- but there are no known reductions from $B$ to $A$.

Even better if there are arguments for supporting these, e.g. there are results that $B$ does not reduce to $A$ assuming some conjectures in complexity theory or cryptography.

Are there any natural examples of such problems?

Example: Graph Isomorphism problem and Integer Factorization problem are conjectured to be in $\mathsf{NPI}$ and there are argument supporting these conjectures. Are there any decision problems harder than these two but not known to be $\mathsf{NP}$-hard?

$\endgroup$
  • 3
    $\begingroup$ Posted here based on Kaveh's suggestion after a CS Stackexchange bounty expired without satisfactory answer. $\endgroup$ – Mohammad Al-Turkistany Jan 29 '13 at 13:40
  • $\begingroup$ Copy on Computer Science. $\endgroup$ – Kaveh Jan 29 '13 at 21:02
18
$\begingroup$

Group Isomorphism $\leq_m$ Graph Isomorphism $\leq_m$ Ring Isomorphism. Also Integer Factoring $\leq_m$ Ring Isomorphism [Kayal and Saxena]. Also Graph Automorphism $\leq_m$ Graph Isomorphism.

Not only are there no known reductions the other way, but there is provably no $\mathsf{AC}^0$-reduction from Graph Iso to Group Iso [Chattopadhyay, Toran, and Wagner].

Note that a reduction from Ring Isomorphism to Graph Isomorphism would also provide a reduction from Integer Factoring to Graph Isomorphism. To me, such a reduction would be surprising though perhaps not shocking.

(For Graph Automorphism vs Graph Isomorphism, their counting versions are known to be equivalent to one another and equivalent to deciding Graph Isomorphism. However, that's not necessarily saying much, as the counting version of bipartite matching is equivalent to the counting version of SAT.)

I don't think there is a real consensus as to which, if any, of these are actually in $\mathsf{P}$. If any of these problems is $\mathsf{NP}$-complete then $\mathsf{PH}$ collapses to the second level. If factoring is $\mathsf{NP}$-complete, then it collapses to the first level, i.e. $\mathsf{NP} = \mathsf{coNP}$.

Also, I seem to recall that using techniques similar to Ladner one can show that any countable partial ordering can be embedded in the ordering $\leq_{m}$ on the problems in $\mathsf{NP}$ (so it's not just a hierarchy, but an arbitrarily complicated countable partial order).

$\endgroup$
  • 1
    $\begingroup$ I find the silent mixing of counting versions and decision versions quite confusing. A ring is a finite structure, and the (decision version of) isomorphism of finite structures is GI-complete. So the decision version of ring isomorphism is neither harder than GI nor harder than integer factoring. $\endgroup$ – Thomas Klimpel Dec 15 '14 at 18:33
  • 1
    $\begingroup$ @ThomasKlimpel: Just b/c iso of finite structures is GI-complete doesn't mean that for any particular class of finite structures, the iso problem is GI-complete. Viz. group iso is not known nor believed to be GI-complete. Ring iso when given by addition/mult tables is also unlikely to be GI-complete, given that it's in $TIME(O(n^{\log n}))$. The version of RingIso I refer to in the answer above is that given by gens and relations. $\endgroup$ – Joshua Grochow Dec 15 '14 at 22:45
  • $\begingroup$ @ThomasKlimpel: If by "silent mixing" you are referring to the parenthetical paragraph, the equivalences referred to there are in terms of polynomial-time Turing reductions (aka Cook reductions), not many-one reductions. $\endgroup$ – Joshua Grochow Dec 15 '14 at 22:50
  • $\begingroup$ OK, I have read the beginning of the reference now. The ring is given by addition/mult tables, but these have a canonical compressed representation for rings (because the additive group is Abelian), so the GI-completeness result for finite structures is not relevant. I wouldn't characterize this representation as "gens and relations", because that sounds like the "silent mixing" about which I initially complained. Unrelated remark: I neither referred to the parenthetical paragraph, nor assumed that ring isomorphism should be GI-complete, just that it should not be harder than GI. $\endgroup$ – Thomas Klimpel Dec 16 '14 at 0:26
  • $\begingroup$ @ThomasKlimpel: Sorry, you're right, it's not quite gens and relations. (And I misread your remark about GI-complete vs "not harder than GI".) I thought I understood what you meant by "silent mixing", but given your last comment I no longer understand. But perhaps this isn't so germane to cstheory.stackexchange and you could email me directly to help clarify my understanding (after which I could update the answer if necessary). $\endgroup$ – Joshua Grochow Dec 16 '14 at 20:18

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.