Are there problems in NP which are not NP-complete but polynomial time algorithm is unknown?

The class of problems that are neither in [math]P[/math] nor [math]NP[/math]-complete([math]NPC[/math]) are called as [math]NP[/math]-intermediate ([math]NPI[/math]). If [math]NPI[/math] is non-empty, obviously [math]P \neq NP[/math]. What's remarkable, the converse also holds. Ladner[1] showed that if [math]P \neq NP[/math], then [math]NPI[/math] is non-empty. Hence [math]P[/math] vs [math]NP[/math] problem reduces to showing the emptyness (or otherwise) of [math]NPI[/math]. Since the most celebrated question of Theoretical Computer Science still stands open, we still don't know of any NP problem which is not NP-complete. However, there are many NP problems that are thought to be not NP-complete. The two most famous example are that of Graph Isomorphism[2] and Integer Factorization[3]. Graph Isomorphism is the problem of determining whether two graphs are isomorphic to each other or not. Integer Factorization is the problem of factoring a number into its prime factors. Coming to primality of a number, before AKS primality test was discovered, this problem was thought to be in class NPI. AKS primality test proved that it is actually in P. Summing up, yes, there are NP problems that are not known to be NP-complete neither P. Since they are also not known to be in P, a polynomial time algorithm, till date, doesn't not exists. [1] @http://en.wikipedia.org/wiki/NP-intermediate [2] http://en.wikipedia.org/wiki/Graph_isomorphism_problem [3] http://en.wikipedia.org/wiki/Integer_factorization