Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? Artificial examples coming directly from the proof of Ladner's theorem do not count.
Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?
Here's a collection of some of the responses of problems between P and NPC:
The sums of square roots problem: Given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, is $A := \sum_i \sqrt{a_i}$ less than, equal to, or greater than $B := \sum_i \sqrt{b_i}$?
The problem has a trivial $O(n)$-time algorithm on the real RAM—Just compute the sums and compare them!—but this does not imply membership in P.
There is an obvious finite-precision algorithm, but it is not known whether a polynomial number of bits of precision is sufficient for correctness. (See https://topp.openproblem.net/p33 for details.)
The Pythogorean theorem implies that the length of any polygonal curve whose vertices and integer endpoints is a sum of square roots of integers. Thus, the sum-of-roots problem is inherent in several planar computational geometry problems, including Euclidean minimum spanning trees, Euclidean shortest paths, minimum-weight triangulations, and the Euclidean traveling salesman problem. (The Euclidean MST problem can be solved in polynomial time without resolving the sum-of-roots problem, thanks to the underlying matroid structure and the fact that the EMST is a subgraph of the Delaunay triangulation.)
There is a polynomial-time randomized algorithm, due to Johannes Blömer, to decide whether the two sums are equal. However, if the answer is no, Blömer's algorithm does not determine which sum is larger.
The decision version of this problem (Is $A > B$?) is not even known to be in NP. However, Blömer's algorithm implies that if the decision problem is in NP, then it is also in co-NP. Thus, the problem is unlikely to be NP-complete.
My favorite problem in this class (I'll phrase it as a functional problem, but it's easy to turn into a decision problem in the standard way): compute the rotation distance between two binary trees (equivalently, the flip distance between two triangulations of a convex polygon).
A problem that is mentioned neither in this list or the MO list is the turnpike problem. Given a multiset of n(n-1)/2 numbers, each number representing the distance between two points on the line, reconstruct the positions of the original points.
Note that what makes this nontrivial is that for a given number d in the multiset, you don't know which pair of points is d units apart.
While it is known that for any given instance there are only a polynomial number of solutions, it is not known how to find one !
Here is a list of problems that may or may not qualify as "sufficiently" different. By the same proof as for Graph Isomorphism, if any of them is NP-complete, then the Polynomial Hierarchy collapses to the second level. I do not think there is any broad consensus as to which of these "ought" to be in P.
The Minimum Circuit Size Problem (MCSP) is my favorite "natural" problem in NP that's not known to be NP-complete: Given the truth-table (of size n=2^m) of an m-variate Boolean function f, and given a number s, does f have a circuit of size s? If MCSP is easy, then there is no cryptographically-secure one-way function. This problem and its variants provided much of the motivation for the study of "brute-force" algorithms in Russia, leading to Levin's work on NP-completeness. This problem can also be viewed in terms of resource-bounded Kolmogorov complexity: asking if a string can be recovered quickly from a short description. This version of the problem was studied by Ko; the name MCSP was used first by Cai and Kabanets, as far as I know. More references can be found in some papers of mine: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf
Monotone self-duality
For any boolean function $f=f(x_1, x_2, ..., x_n)$, it's dual is $f^d=\bar{f}(\bar{x_1}, \bar{x_2}, ..., \bar{x_n})$. Given $f(x_1, x_2, ..., x_n)$ represented by a CNF formula, we have to decide whether $f=f^d$.
This problem is in co-NP[$\log^2 n$], i.e., it is decidable with $O(\log^2n/ \log\log n)$ nondeterministic steps. Thus, it has a quasi-polynomial time algorithm ($O(n^{\log n/\log \log n})$ time), and hence is unlikely to be co-NP-hard.
It is still open whether this problem is in P or not. More details can be found in the 2008 paper "Computational aspects of monotone dualization: A brief survey" by Thomas Eiter, Kazuhisa Makino, and Georg Gottlob.
Knot triviality: Given a closed polygonal chain in 3-space, is it unknotted (ie, ambient-isotopic to a flat circle)?
This is known to be in NP by deepish results in normal surface theory, but no poly-time algorithm or NP-hardness proof is known.
It is not known if it is possible to decide in polynomial time if player 1 has a winning strategy in a parity game (from a given starting position). The problem is, however, contained in NP and co-NP and even in UP and co-UP.
In a monotone CNF formula every clause contains only positive literals or only negative literals. In an intersecting monotone CNF formula every positive clause has some variable in common with every negative clause.
The decision problem
INTERSECTING MONOTONE SAT
Input: intersecting monotone CNF formula $f$
Question: is $f$ satisfiable?
has an $n^{o(\log\ n)}$ algorithm dating back to 1996, but is not known to be in P. (Of course, it might turn out to be in P, but that would be a major result.)
You get a very long list of problems if willing to accept approximation problems, such as approximating Max-Cut to within a factor 0.878. We don't know if it's NP-hard or in P (only know NP-hardness assuming the Uniuqe Games Conjecture).
The Pigeonhole Version of Subset Sum (or Subset Sum Equality).
Given:
$$a_k \in \mathbb{Z}_{>0}$$ $$\sum_{k=0}^{n-1} a_k < 2^n - 1$$
By the pigeonhole principle, there must exist two disjoint subsets, $S_1, S_2 \subseteq \{ 1, \dots, n \} $ such that:
$$\sum_{j \in S_1} a_j = \sum_{k \in S_2} a_k $$
The pigeonhole subset sum problem asks for such a solution. Originally stated in "Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem" by Bazgan, Santha and Tuza.
There are a lot of problems related to finding hidden subgroups. You mentioned factoring, but there is also the discrete log problem as well as others related to elliptic curves, etc.
Here's a problem in computational social choice which is not known to be in P, and may or may not be NP-complete.
Agenda control for balanced single-elimination tournaments:
Given: tournament graph $T$ on $n=2^k$ nodes, node $a$
Question: does there exist a permutation of the nodes (a bracket) so that a is the winner of the induced single-elimination tournament?
Given a permutation $P_k$ on $2^k$ nodes of $V$ and a tournament graph $T$ on $V$, one can obtain a permutation $P_{k-1}$ on $2^{k-1}$ nodes as follows. For every $i>0$, consider $P_k[2i-1]$ and $P_k[2i]$ and the arc $e$ between them in $T$; let $P_{k-1}[i]=P_k[2i-1]$ if $e=(P_k[2i-1],P_k[2i])$ and $P_{k-1}[i]=P_k[2i]$ otherwise. That is, we match up pairs of nodes according to $P_k$ and use $T$ to decide which nodes (winners) move on to the next round $P_{k-1}$. Hence given a permutation on $2^k$ one can actually define $k$ rounds $P_{k-1},\ldots,P_0$ inductively as above, until the last permutation contains only one node. This defines a (balanced) single-elimination tournament on $2^k$ nodes. The node which remains after all the rounds is the winner of the tournament.
Agenda control for balanced single-elimination tournaments (graph formulation):
Given: tournament graph $T$ on $n=2^k$ nodes, node $a$
Question: does $T$ contain a (spanning) binomial arborescence on $2^k$ nodes rooted at $a$?
A binomial arborescence on $2^k$ nodes rooted at a node $x$ is defined recursively as $a$ binomial arborescence on $2^{k-1}$ nodes rooted at $x$ and a binomial arborescence on $2^{k-1}$ nodes rooted at a different node $y$ and an arc from $x$ to $y$. (If $k=0$, a binomial arborescence is just the root.) The spanning binomial arborescences in a tournament graph capture exactly the single-elimination tournaments which can be played, given the match outcome information in the tournament graph.
Some references:
Take a look at the class TFNP. It has a lot of search problems with an intermediate status.
The induced subgraph isomorphism problem has NP-incomplete "left-hand side restrictions" assuming that P is not equal to NP. See Y. Chen, M. Thurley, M. Weyer: Understanding the Complexity of Induced Subgraph Isomorphisms, ICALP 2008.
The complexity of planar Minimum Bisection problem is an intriguing open problem which is not known to be $NP$-hard. In contrast, the planar Maximum Bisection problem is $NP$-hard.
Minimum Bisection problem: Find a partition of the set of nodes into two equal size parts such that the number of crossing edges is minimized.
Karpinski, Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
The cutting stock problem with a constant number of object lengths. See this discussion for more information.
The gap version of the closest vector in lattice problem is the following: Given a basis for an $n$-dimensional lattice and a vector $v$, distinguish between the two cases where there is a lattice vector at distance at most one $1$ from $v$ or when every lattice vector is $\beta$-far from $v$, for some fixed gap parameter $\beta > 1$.
When $\beta = \sqrt{n}$, the problem is in $\mathsf{NP} \cap \mathsf{coNP}$ and thus unlikely to be $\mathsf{NP}$-complete (and is conjectured to be outside $\mathsf{P}$). This case is of central attention for lattice-based cryptography and the related dihedral hidden subgroup problem in quentum computing. When $\beta$ is much smaller, say $\beta = n^{o(1/\log \log n)}$, the problem becomes $\mathsf{NP}$-hard.
A graph $G = (V,E)$ is said to be labeled by $f$ if each vertex $v\in V$ is assigned a non-negative integer value $f(v)$ and each edge $e = uv\in E$ is assigned the value $|f(u) − f(v)|$. The labeling is graceful if $f : V\rightarrow \{0, 1, 2,\dots, |E|\}$ is an injection and if all edges of G have distinct labels from $\{1, 2,..., |E|\}$. A graph is said to be graceful if it admits a graceful labeling. The computational complexity of deciding whether a graph is graceful is not known.
The problem of finding Vapnik–Chervonenkis dimension is not known to be in $P$ neither known to be $NP$-complete. The problem can be solved by quasi-polynomial time algorithm ($ O(n^{\log n})$). The problem can not be $NP$-complete unless $NP$ is contained in Quasi-polynomial time.
In the linear divisibility problem, the input is two integers $a$ and $b$ and the task is to determine whether there exists an integer of the form $a \cdot x+1$ that divides $b$.
The linear divisibility problem is known to be $\gamma$-complete for NP but not known (AFAIK) to be NP-complete.
Garey and Johnson in their seminal "Computers and Intractability" say that (pp. 158-159):
A $\gamma$-reduction, in contrast to our other notions of reducibility, is nondeterministic in nature. Let us first introduce the notion of the relation $R_M$ computed by an NDTM program $M$:$$R_M=\{\langle x,y\rangle:there\ is\ a\ string\ z\ such\ that\ on\ input\ x\ and\ guess\ z\ M\ has\ output\ y\}$$ (where the definition of "output" is as in the computation of functions by DTMs).
We say that a language $L_1$ over alphabet $\Sigma_1$ is $\gamma$-reducible to a language $L_2$ over $\Sigma_2$ (written $L_1\propto_{\gamma}L_2$) if there is a polynomial time NDTM program $M$ such that for all $x\in\Sigma_1^*$ there is some $y\in\Sigma_2^*$ for which $\langle x,y\rangle\in R_M$ and such that for all $\langle x,y\rangle\in R_M$, $x\in L_1$ if and only if $y\in L_2$. In other words, there is at least one halting computation for $M$ on every input $x$ and, given an input $x$, all halting computations on $x$ yield outputs that are in $L_2$ if and only if $x\in L_1$.
The problem of finding a minimum dominating set in tournament is not known to be in $P$ neither known to be $NP$-complete. The problem has quasi-polynomial time algorithm ($ O(n^{\log n})$). If the problem has polynomial time algorithm then satisfiability can be solved in sub-exponential time.
The following problem is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of: $$p(x) = r^x $$ (or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.
Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate as well.
For additional details see my question and related discussion.
I don't know whether the weighted hypergraph isomorphism problem proposed in the answer by Thinh D. Nguyen cannot be simply shown to be GI complete. However, there is a GI-hard problem closely related to GI, which has not been reduced to GI yet, namely the string isomorphism problem (also called color isomorphism problem). This is the problem actually shown to be in quasi-polynomial time by László Babai. It is of independent interest, since it is equivalent to a number of decision problems in (permutation) group theory:
A problem that is not known to be either in FP or to be NP-hard is the problem of finding a minimal Steiner tree when the Steiner vertices are promised to fall on two straight line segments intersecting at an angle of 120°. If the angle between the line segments is less than 120°, then the problem is NP-hard. It is conjectured that when the angle is greater than 120°, then the problem is in FP.
Hence the following decision problem currently appears to be of intermediate complexity:
Minimal 120°-Steiner tree
Input: a finite set of points in the plane, lying on two line segments intersecting at an angle of 120°, and a positive rational number $q$.
Question: is there a Steiner tree of total length at most $q$?
Of course, this may actually be in P or be NP-complete, but then it seems we would have an interesting dichotomy at 120° instead of an intermediate problem. (The conjecture may also be false.)
A GI-hard problem not known to be NP-complete could be WEIGHTED_HYPERGRAPH_ISOMORPHISM. You are given two hypergraphs $G_1$ and $G_2$ on $n$ vertices with weighted hyper-edges, decide if there is a vertex permutation $\pi$ turning $G_1$ into $G_2$. See also: GI-hard graph problem not known to be $NP$-complete
A handful of natural problems are (promise) $\mathsf{BQP\:complete}$, and thus are not likely to be $\mathsf{NP\:complete}$ under the reasonable hypothesis that $\mathsf{NP}\not\subseteq\mathsf{BQP}$.
Adjusting the hypotheses to remove negative signs might negate the strength provided by interference, landing the problem in $\mathsf{NP}$ and not empowering it to be $\mathsf{BQP\:complete}$.
For example estimating an entry $(A^m)_{ij}$ of the $m^{th}$ power of a large, sparse matrix $A$ with $\mathcal{O}(\exp m)$ entries $A_{ij}\in\{-1,0,1\}$ is $\mathsf{BQP\: complete}$, as shown here.
I believe that when the entries $A_{ij}\in\{0,1\}$, e.g. when $A$ is an adjacency matrix of a large graph and $(A^m)_{ij}$ counts the number of $m$-length walks from vertex $i$ to vertex $j$, the estimation is amenable to Stockmeyer approximation, and thus likely in $\mathsf{AM}$, but still not $\mathsf{NP\:complete}$.
The Coffman–Graham algorithm solves scheduling N jobs (with unit length and DAG dependency) on K=2 machines with minimal span in polynomial time. When K is not a constant, the problem is known to be NPC. However, when K is a constant like 3, the problem is not known to be in P or NPC.
