In our previous lectures we studied complexity classes P and

In our previous lectures we studied complexity classes P and NP, as well as NP-complete problems. The relations between those classes are shown in the following diagram: Are there any problems that belong to the class NP, but lay outside both P and NP-complete (i.e. in the purple area of the diagram)? Can you name any such problem (or at least a problem that is suspected to belong to the purple area)? Find a reference to a paper or webpage with answers

Solution

The given diagram is kind of diagram of complexity classes provided that P NP (not in P and not NP Complete?). The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by Ladner\'s theorem. Please refer wikipedia for Ladner\'s thearom. The answer is No, this is unknown (with the exception of the trivial languages and , these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an NPNP problem which is not complete for NPNP w.r.t. many-one polynomial time reductions would imply that PNPPNP which is not known (although widely believed). If the two classes are different then we know that there are problems in NPNP which are not complete for it, take any problem in PP.