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.pdf

Ill 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

_________________

The notation NP stands for “nondeterministic polynomial time”, since originally
NP was defined in terms of nondeterministic machines (that is, machines
that have more than one possible move from a given configuration).
However now it is customary to give an equivalent definition using the notion
of a checking relation, which is simply a binary relation R ⊆ Σ∗ × Σ∗
1
for some finite alphabets Σ and Σ1. We associate with each such relation R
a language LR over Σ ∪ Σ1 ∪ {#} defined by
LR = {w#y | R(w, y)}
where the symbol # is not in Σ. We say that R is polynomial-time iff LR ∈ P.
Now we define the class NP of languages by the condition that a language
L over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation
R such that for all w ∈ Σ∗,
w ∈ L ⇐⇒ ∃y(|y| ≤ |w|k and R(w, y))
where |w| and |y| denote the lengths of w and y, respectively.

_________________

Problem Statement: Does P = NP?
It is easy to see that the answer is independent of the size of the alphabet Σ
(we assume |Σ| ≥ 2), since strings over an alphabet of any fixed size can be
efficiently coded by strings over a binary alphabet. (For |Σ| = 1 the problem
is still open, although it is possible that P = NP in this case but not in the
general case.)
It is trivial to show that P ⊆ NP, since for each language L over Σ, if L ∈ P
then we can define the polynomial-time checking relation R ⊆ Σ∗∪ Σ∗
by
R(w, y) ⇐⇒ w ∈ L
for all w, y ∈ Σ∗.

Here are two simple examples, using decimal notation to code natural numbers: The set of perfect squares is in P and the set of composite numbers is
in NP (and not known to be in P). For the latter, the associated polynomial
time checking relation R is given by
R(a, b) ⇐⇒ 1 < b < a and b|a (1)
In general the decimal notation for a natural number c is denoted by c.

_________________

The importance of the P vs NP questions stems from the successful theories of NP-completeness and complexity-based cryptography, as well as the
potentially stunning practical consequences of a constructive proof of P =
NP.
The theory of NP-completeness has its roots in computability theory, which
originated in the work of Turing, Church, G¨odel, and others in the 1930’s.
The computability precursors of the classes P and NP are the classes of
decidable and c.e. (computably enumerable) languages, respectively. We
say that a language L is c.e. (or semi-decidable) iff L = L(M) for some
Turing machine M. We say that L is decidable iff L = L(M) for some Turing
machine M which satisfies the condition that M halts on all input strings
w. There is an equivalent definition of c.e. which brings out its analogy with
NP, namely L is c.e. iff there is a computable “checking relation” R(x, y)
such that L = {x | ∃yR(x, y)}.
Using the notation M to denote a string describing a Turing machine M,
we define the Halting Problem H P as follows:
H P = {M | M is a Turing machine which halts on input M}
Turing used a simple diagonal argument to show that H P is not decidable.
On the other hand, it is not hard to show that H P is c.e.
Of central importance in computability theory is the notion of reducibility,
which Turing defined roughly as follows: A language L1 is Turing reducible
to a language L2 iff there is an oracle Turing machine M which accepts L1,
where M is allowed to make membership queries of the form x ∈ L2? which
are correctly answered by an “oracle” for L2. Later the more restricted notion
of many-one reducibility (≤m) was introduced and defined as follows.
Definition 1: Suppose that Li is a language over Σi, i = 1, 2. Then L1 ≤m L2 iff there is a (total) computable function f : Σ∗ 1 → Σ∗2 such that x ∈ L1 ⇐⇒ f(x) ∈ L2, for all x ∈ Σ∗1.
It is easy to see that if L1 ≤m L2 and L2 is decidable, then L1 is decidable.
This fact provides an important tool for showing undecidability; for example
if H P ≤m L then L is undecidable.

_________________

Are you a quantum engineer?

Yes Im a computer, and there is not much to do with quantum mechanics in most of this, the top just puts your mind into gear to prepare for the P vs NP stuff. Its quite fun, Im just waiting for someone who understands it. :3

_________________

I only said quantum engineering because i gave up reading all of it because I had no clue whatsoever what you were getting at

same here chris

_________________



Leader of the Might City of Varlos

If I got what it meant i would probably be really into what your trying to communicate but I don't learn this stuff in year 9... Makes algebra look like kiddies work

Does: http://www.claymath.org/millennium/P_vs ... iption.pdf educate you to understand what you're saying?

Thats just a starting point, the true challenge is going beyond that, large portions of that are copyed into here in order to give a basic idea. You need to break beyond it into a theoretical possibilities area such as stellar measurements or quantum mechanics. Im working on it with my friend, but we got a bit sidetracked into making a nuclear reactor...

_________________

Oh trust...How I couldn't have seen that coming
I might actually read the link and try doing it -.-
I'll probably fail but I wanna at least give it a shot.