If it is done in polynomial time, then it would by definition be in P which means it would NOT be NP complete unless P=NP.

I think you are trying to ask how it could be done in less than exponential time (which is how fast the fastest algorithms to solve NP complete problems run).

I personally would expect an algorithm to perform the match would run in O(U*US+K*KS+UI*KI*U) where U=the number of unknown (ie flickr pictures), K=the number of known pictures, US=the average size of an unknown picture, K=the size of the average known picture, UI=the number of interesting things in an unknown picture and KI=the number of interesting things in a known picture. However, it would often run faster because it should be fairly easy to disqualify two pictures as containing any of the same interesting features.