Exponential Bitstring

A simple example of the exponential problem.
Given a bit string S of length N what is the probability to guess the value of the string ?

2^-N

OK.
Given a set U of M bitstrings of length N and a string Su of U what is the probability to guess Su in U ?

1/M

Now if U is the set of all finite bitstrings available in an environment ( like the real world ) containing the problem and the solver what is the probability to find the solution for the problem ?

The key is that we are inside U and all the machines are inside U we can not construct bitstrings outside U ! and this is indipendently of deterministic or stochastic assumptions.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s