Channels ▼

Cameron and Tracey Hughes

Dr. Dobb's Bloggers

Search Space ... the final frontier

March 04, 2009

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, 263 x 369, 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?

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.