This is how Wikipedia describes NP-complete problems:
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial-time, and also in the set of NP-hard problems so that any NP problem can be converted into L by a transformation of the inputs in polynomial-time.Note that it says, "As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today." I haven't seen the proof for it, but I've also heard that if you could prove that one NP-complete problem does not have a polynomial-time solution to it, then that would prove that none of them have a polynomial-time solution to them. The theory is a little over my head, but I'm going to take a shot.
Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.
While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using approximation algorithms.
I'd like to propose a problem that is NP-complete and show that it does not have a polynomial-time solution to it. Imagine I pick an n-tuple of random 32-bit, unsigned integers. Your job is guess what the n-tuple is. Hence, where n is 2, I might pick (376, 792), and your job is to guess that tuple. If you guess a certain tuple, I can tell you whether you're right or not. Hence, I can verify a solution in polynomial-time (it takes me O(n) number of int comparisons to verify a solution). However, to try to solve such a problem, you either have to get really lucky or you have to brute force it. If you find a method other than brute force trying every possible solution, then obviously there's something wrong with my random number generator. To use brute force to guess the solution requires O(A^n) for some constant A. Since it's "to the n", it's not polynomial-time (3nA^3 is polynomial-time since the exponent is fixed; A^n is not polynomial-time since the exponent varies with the size of n).
Now I know that some of you reading this understand the computer science a lot better than I do. Have I actually shown (at least informally) that NP-complete problems are really NP-complete? If not, can you, in lay man's terms explain what I'm misunderstanding? Thanks!