What is the complexity class NPI?

Question

Studying complexity, I came across the term NPI. It means NP-intermediate. But I didn’t understand what this "intermediary is".

• What characterizes an NPI problem? Why does it have that name?
• There is difference between NPI and NPC?
• Something changes regarding this class if the answer to the problem is found P vs NP?

---

• More about NPC and P vs NP: What is a complete NP problem?
• Mini-glossary to help with research (more details on existing @Victorstafusa response):
  • NP: nondeterministic polynomial
  • P: deterministic polynomial
  • NPC: NP-complete
  • NPI: NP-intermediary

Answer 1

P problems are those that admit deterministic solution in polynomial time.

NP problems are those that admit solution nay-deterministic in polynomial time (i.e., if you see a possible answer in a crystal ball, you can check whether or not it is correct in polynomial time).

The NP-complete problems (NPC) are the "most difficult of NP", reducing themselves in polynomial time to each other. There are several known NP-complete problems out there, such as satisfiability, traveling salesman, Hamiltonian path, etc. If one of them is shown to be in P, then all NP problems would be in P and with it P = NP.

However, taking the premise that P NP, comes the question: Are all the problems that are in NP necessarily in P or NPC? Or would there be problems in NP that are not in either of these two categories? That’s where NPI comes in.

The class NPI corresponds to the set of problems that are in NP, but are neither in NPC nor in P. These are problems for which there is no deterministic solution in polynomial time (they are not in P), but still a possible solution can be verified in polynomial time (are in NP) and are not NP-complete:

Richard Ladner demonstrated in 1975 that if P NP then there are problems within NP that are neither in P nor in NPC, it is with it that the NPI class emerged. It has this name (intermediate NP) because it is neither the most difficult of NP (NPC) nor the easiest (P). Therefore, they are in an intermediate category.

There are no real problems that are definitely in NPI. Because if to prove that a problem is NPI, you would have to prove that it is in NP, but it is out of P, and with that you would have to prove first that P NP before proving that any particular problem is in NPI. Despite this, there are some problems suspected to be in this area, the most celebrated are:

• Factorization of numbers
• Discrete logarithm
• Isomorphism of graphs

Let us take the problem of factoring:

• Be it x the number you want to factor in. If you see in a crystal ball a sequence of primes that are supposedly multiplied result in x, you can easily do the multiplication and check whether in fact they produce or not x, so this problem is in NP.

• There is no known efficient algorithm for factoring large numbers. Assuming in fact none exists, then this problem is not in P.

• There is no known way to reduce the satisfiability problem to the polynomial-time factorization problem, and assuming that such a reduction does not actually exist, the factorization problem is not NPC. In fact, NPC problems seem to be significantly more complex than factorization.

• Therefore, if these assumptions are true, the factorization problem is NPI.