NP/NP complete and AI-complete problems are problems with huge or even infinite search or state spaces. The search or state space is a graph (or other representation) that contains all of the possible states (including the initial and goal states of the problem) of the domain of the initial problem. An example of a huge search space is all the nodes on the Internet ...

... a reported 5 million nodes back in 2007 as represented in this image. An infinite search space would be something like proving a theorem.

Consider this, what if we are to guess a 12 character code you were thinking. The first three character had to be letters and the remaining 9 can be any mixture of letters and digits (with replacement). An exhaustive search in such spaces would require examining all sequences of n moves where the number of n moves would grow exponentially (in this case, 26³ x 36⁹, a huge number). And boom, a combinatorial explosion! The critical problem of searching for paths/solutions within such a huge search space is the amount of time and space it would take. Can we use massive multicore to help with such a problem, can multicore overcome combinatorial explosion? For this problem, codes can be generated independently and in parallel. Each core could be used to create codes with certain patterns, codes ending with digits, codes ending with letters, code starting with certain letters, etc. Is such an approach plausible?