<p>Group Isomorphism <span class="math-container">$\leq_m$</span> Graph Isomorphism <span class="math-container">$\leq_m$</span> Code Equivalence (Permutational or Monomial) <span class="math-container">$\leq_m$</span> Tensor Isomorphism <span class="math-container">$\equiv_m$</span> Ring Isomorphism. Also Integer Factoring <span class="math-container">$\leq_m$</span> Ring Isomorphism [<a href="http://eccc.hpi-web.de/report/2004/109/" rel="nofollow noreferrer">Kayal and Saxena</a>]. The reduction GI to CodeEq is <a href="https://ieeexplore.ieee.org/document/623157" rel="nofollow noreferrer">Petrank &amp; Roth</a>; CodeEq to Tensor Iso and Tensor Iso to Ring Iso is <a href="https://dx.doi.org/10.4230/LIPIcs.ITCS.2021.31" rel="nofollow noreferrer">G-Qiao</a>.</p>
<p>Also Graph Automorphism <span class="math-container">$\leq_m$</span> Graph Isomorphism.</p>
<p>Not only are there no known reductions the other way, but there is provably no
<span class="math-container">$\mathsf{AC}^0$</span>-reduction from Graph Iso to Group Iso [<a href="http://eccc.hpi-web.de/report/2010/117/" rel="nofollow noreferrer">Chattopadhyay, Toran, and Wagner</a>].</p>
<p>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 very surprising.</p>
<p>(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.)</p>
<p>I don't think there is a real consensus as to which, if any, of these are actually in <span class="math-container">$\mathsf{P}$</span>. If any of these problems is <span class="math-container">$\mathsf{NP}$</span>-complete then <span class="math-container">$\mathsf{PH}$</span> collapses to the second level. If factoring is <span class="math-container">$\mathsf{NP}$</span>-complete, then it collapses to the first level, i.e. <span class="math-container">$\mathsf{NP} = \mathsf{coNP}$</span>.</p>
<p>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 <span class="math-container">$\leq_{m}$</span> on the problems in <span class="math-container">$\mathsf{NP}$</span> (so it's not just a hierarchy, but an arbitrarily complicated countable partial order).</p>

CC BY-SA 3.0
2014-12-15T18:33:11.417Z
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.
Thomas Klimpel
CC BY-SA 3.0
2014-12-15T22:45:13.113Z
@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.
Joshua Grochow
CC BY-SA 3.0
2014-12-15T22:50:53.883Z
@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.
Joshua Grochow
CC BY-SA 3.0
2014-12-16T00:26:05.607Z
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.
Thomas Klimpel
CC BY-SA 3.0
2014-12-16T20:18:10.530Z
@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).
Joshua Grochow
CC BY-SA 4.0
2013-01-29T17:43:36.700Z
2021-11-19T08:10:33.480Z
2021-11-19T08:10:33.480Z
Joshua Grochow
<p>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}$ <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/">here</a>. </p>

<p><a href="https://cstheory.stackexchange.com/questions/799/generalized-ladners-theorem">Ladner's theorem</a> 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.</p>

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

<p>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.</p>

<p>Are there any <em>natural</em> examples of such problems?</p>

<p>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?</p>

CC BY-SA 3.0
2013-01-29T21:02:56.413Z
[Copy](http://cs.stackexchange.com/questions/78/natural-candidates-for-the-hierarchy-inside-npi) on [cs.se].
Kaveh
<cc.complexity-theory><np-hardness><np-intermediate>
Natural candidates for the hierarchy inside NPI
Mohammad Al-Turkistany
# Natural candidates for the hierarchy inside NPI

(Asked by: username_0 on 2013-01-29)

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](https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/).

[Ladner's theorem](https://cstheory.stackexchange.com/questions/799/generalized-ladners-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?

**Tags:** cc.complexity-theory, np-hardness, np-intermediate

> **Comments:**
> **username_1**: [Copy](http://cs.stackexchange.com/questions/78/natural-candidates-for-the-hierarchy-inside-npi) on [cs.se].  

---

## 1 answers

### Answer by username_2 on 2013-01-29. Score: 19 | Accepted answer

Group Isomorphism $\leq\_m$ Graph Isomorphism $\leq\_m$ Code Equivalence (Permutational or Monomial) $\leq\_m$ Tensor Isomorphism $\equiv\_m$ Ring Isomorphism. Also Integer Factoring $\leq\_m$ Ring Isomorphism [[Kayal and Saxena](http://eccc.hpi-web.de/report/2004/109/)]. The reduction GI to CodeEq is [Petrank & Roth](https://ieeexplore.ieee.org/document/623157); CodeEq to Tensor Iso and Tensor Iso to Ring Iso is [G-Qiao](https://dx.doi.org/10.4230/LIPIcs.ITCS.2021.31).

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](http://eccc.hpi-web.de/report/2010/117/)].

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 very surprising.

(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).

> **Comments:**
> **username_3**: 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.  
> **username_2**: @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.  
> **username_2**: @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.  
> **username_3**: 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.  
> **username_2**: @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).  

---

