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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
19
$\begingroup$

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]. The reduction GI to CodeEq is Petrank & Roth; CodeEq to Tensor Iso and Tensor Iso to Ring Iso is G-Qiao.

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

Improve this answer
$\endgroup$
5
  • 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
    Commented Dec 15, 2014 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
    Commented Dec 15, 2014 at 22:45
  • 1
    $\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
    Commented Dec 15, 2014 at 22:50
  • 1
    $\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
    Commented Dec 16, 2014 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
    Commented Dec 16, 2014 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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