Antibodies, Charles Stross wrote a, 2000
A short story called "Antibodies" that hinges on the fact that solving P=NP is a required prerequisite for developing a computer intelligence. It's available in his book Toast. Stross has put the full text of this book online. (This link will take you directly to the story.)
And according to Stross's site, the story was:
Published in Interzone #157; republished in "The Year's Best Science Fiction #18" (ed. Gardner Dozois). Mentioned in Locus' "Recommended Reading List" for 2000. Shortlisted for the 2001 Theodore Sturgeon Award (lost to Ian MacDonald's "Tendoleo's Story").