23
$\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$
17
  • 1
    $\begingroup$ So you are looking for problems $P \in \mathrm{NP}$ such that $P_1 \leq_p P \leq_p P_2$ with $P_1 \in \mathrm{NPI}$ and $P_2 \in \mathrm{NPC}$? $\endgroup$
    – Raphael
    Commented Mar 7, 2012 at 7:46
  • 1
    $\begingroup$ Yes but there is no known reduction from P to P1 (similarly no known reduction from P2 to P). $\endgroup$
    – Mohammad Al-Turkistany
    Commented Mar 7, 2012 at 7:58
  • 2
    $\begingroup$ there are several problems with a status similar to factoring, see this paper by Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf $\endgroup$
    – Marcos Villagra
    Commented Mar 7, 2012 at 8:42
  • 8
    $\begingroup$ besides, we have a very nice list in cstheory cstheory.stackexchange.com/questions/79/… $\endgroup$
    – Marcos Villagra
    Commented Mar 7, 2012 at 8:43
  • 2
    $\begingroup$ why is the list that Marcos links to not the answer to your question ? $\endgroup$
    – Suresh
    Commented Mar 7, 2012 at 16:21

1 Answer 1

Reset to default
5
$\begingroup$

I've found a nice problem called ModularFactorial. Take as input two $n$-digit integers $x$ and $y$, and output $x! \mod y$. This problem is at least as hard as Factoring and not know to be hard for FNP. The reference is the recent (and beautiful) book by Cristopher Moore and Stephan Mertens The Nature of Computation, page 79.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ I believe the OP is looking for problems in NP. Can you reformulate this as a decision problem? $\endgroup$
    – Zach Langley
    Commented Mar 9, 2012 at 12:42
  • $\begingroup$ FNP is the function version (i.e.,search problems) of NP. In fact, factoring is not in NP, it is FNP. For instance, the decision problem for factoring is trivial, the complexity is just O(1), but the search problem is the difficult part. Since the OP gave factoring as an example, I think this is also a valid answer. $\endgroup$
    – Marcos Villagra
    Commented Mar 9, 2012 at 13:19
  • 1
    $\begingroup$ Factoring can be reformulated into a decision problem as follows: given an integer $n$ and an integer $k$, does $n$ contain a factor $d$ with $1 < d \le k$? Is there an analogous decision version of the ModularFactorial problem? $\endgroup$
    – Zach Langley
    Commented Mar 9, 2012 at 14:46
  • $\begingroup$ @Marcos, Thanks. I'm interested in decision problems in NP. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Mar 9, 2012 at 15:31
  • $\begingroup$ @ZachLangley, yes of course I agree, but I was thinking in another decision version, namely, "does x has a factor?". The answer there is just, "yes" always. You can do the same with modularfactorial, give an integer k and decide if $x!\mod y$ is greater than $k$ or not. $\endgroup$
    – Marcos Villagra
    Commented Mar 9, 2012 at 22:43

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.