Before you post make Sure You Understand this! All unrelated posts will be removed!Ok so I've been looking at some Theoretical Computing, and Science. After taking a look at this:
I'm going to assume that you know what bogosort is. If you don't, here's the algorithm:
1.)If the list is sorted, stop.
2.)If it isn't, shuffle the list randomly.
3.)Go back to step 1.
Obviously this is extremely inefficient. However, there's a solution to this inefficiency, and this solution is quantum computing. Because of the many-universes hypothesis in quantum physics, a list that is sorted randomly will create an infinite number of universes, with some universes containing a sorted list. In this case, quantum computing can make bogosort work in O(n). Here's the new algorithm:
1.)Shuffle the list randomly.
2.)If the list is sorted, stop.
3.)If it isn't sorted, destroy the entire universe.
Since the only survivors of this rather apocalyptic approach to computing will be in universes where the list was sorted after the first shuffle, it is quite efficient. Checking if a list is sorted requires n-1 comparisons, and I'm going to assume an entire universe can be destroyed in O(1), as it only ever has to happen once. Thus, bogosort becomes an O(n) sort algorithm.
So you take this, then consider this:
http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdfIll post some definitions here:
P: Informally the class P is the class of decision problems solvable by some
algorithm within a number of steps bounded by some fixed polynomial in
the length of the input. Turing was not concerned with the efficiency of his
machines, but rather his concern was whether they can simulate arbitrary
algorithms given sufficient time. However it turns out Turing machines can
generally simulate more efficient computer models (for example machines
equipped with many tapes or an unbounded random access memory) by at
most squaring or cubing the computation time. Thus P is a robust class,
and has equivalent definitions over a large class of computer models. Here we
follow standard practice and define the class P in terms of Turing machines.
Formally the elements of the class P are languages. Let Σ be a finite alphabet
(that is, a finite nonempty set) with at least two elements, and let Σ∗ be the
set of finite strings over Σ. Then a language over Σ is a subset L of Σ∗. Each
Turing machine M has an associated input alphabet Σ. For each string w in
Σ∗ there is a computation associated with M with input w. (The notions of
Turing machine and computation are defined formally in the appendix.) We
say that M accepts w if this computation terminates in the accepting state.
Note that M fails to accept w either if this computation ends in the rejecting
state, or if the computation fails to terminate. The language accepted by M,
1
denoted L(M), has associated alphabet Σ and is defined by
L(M) = {w ∈ Σ∗ | M accepts w}
We denote by tM(w) the number of steps in the computation of M on input
w (see the Appendix). If this computation never halts, then tM(w) = ∞.
For n ∈ N we denote by TM(n) the worst case run time of M; that is
TM(n) = max{tM(w) | w ∈ Σn}
where Σn is the set of all strings over Σ of length n. We say that M runs in
polynomial time if there exists k such that for all n, TM(n) ≤ nk + k. Now
we define the class P of languages by
P = {L | L = L(M) for some Turing machine M which runs in polynomial time}
NP in next post