ajithor/PvsNP.txt

## PvsNP.txt
Before addressing the big questions, we'll get into what it is based on, so everyone can justify the address.
So let us just look at the world for an instance. The world is filled with questions.

Now, consider a class of problems, that computers can easily solve, call it 'P'. But 'easy' is not an appreciably quantifiable metric. That's when the study of Algorithmic complexities comes in. We can use the big-Oh 'O' notation to quantify 'easy'.
Redifining P, it is the class of algorithms(solutions of a problem) which can be solved in polynomial time.
or P = { solvable problem in polynomial time } (O being quite generous, like O(n^10000) os so)
eg: finding product of 2 numbers, finding gcd, etc. the essence being, that it is just simpler to work the algorithm.

Now, consider a set of problems, whose solution has vast parametric dependability, ergo cannot be solved easily. Which means the complexity of the algorithms is so high, that computers might take ages, arriving at optimal solutions.
Although, provided the solution, it is easy to cross-verify it. eg: given a solved jigsaw puzzle, we can easily verify if it is right; although solving it(from scratch) (or figuring out if it can be solved) will take way too much time (exponential increase of time, with increase in number of pieces). Such problems can be solved, but it cannot be determined polynomially. Should we have a trial-set of values, it is possible to see if it 'provides the right solution' within polynomial time.
tip: a class of machines can be used to verify the parametric values of an algorithm to obtain a value os true.(biased towards 'yes' (biased towards 'no' => co-NP))
So redifining, NP = { decision problems solvable in non-deterministic polynomial time }
[So NP => producing solution is hard, verifying is easy]

Note: other class of problems in the end.

One of the examples of an NP problem is 3SAT (sat-datisfiability, 3-literals)
given a Boolean equation of the form (X1 V X3 V X6) ^ (X2 V X4 V X7) ^ ........
we need to set each Xi = {0,1}, such that the whole equation = true.
check: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability
Simiral problems are Scheduling, Map Coloring, Packing, Puzzles, Protein Folding, Travelling Salesman, CLIQUE.

On the 20th of may, 2000; The Clay Institute of Mathematics announced $1M as prize amount to anyone solving one of 7 following problems:
1. Poincare Conjecture(\/) 2. P versus NP problem 3. Navier-Stokes problem 4. Riemann Hypothesis 5. Brich amd Swinnerton-Dyer conjencture 6. Yang-Mills theory 7. Hodge conjecture
Note: Poincare Conjecture was solved by a Russian Mathematecian, Grigori Perelman in 2003.

As time went, people discovered some algorithms that solved the problems (which was previously thought to be of NP class), within Polynomial time. This lead to the common question that, 'can every problem(that are currently thought to be of NP) be solved within P?' "Can we discover simpler algorithms to every problems that exists in NP, so as to be solved within P?" "for each NP-type problem, does there exist a P-type algorithm, just as there exists NP-type solution to a P-type problem?" "is P eqaul to NP?" "P=NP?"

<b>NP-compeleteness<b> This is perhaps the first (and only) step taken toward addressing the big Question.
People discovered that there existed some NP-type problems, whose core logic was linked to many of the NP-type problems. They found out that any NP-type problem can be converted to form of this problem(reverse is not true). It means that finding a faster way to solve the considred problem eould imply finding a faster way to solve all related NP-type problems. These considred problems are of the class "NP-Compelete".
Tip: There are several NP-compelete problems. eg: SAT, CLIQUE(https://en.wikipedia.org/wiki/Clique_problem)
Takeaway being, any NP-type problem can be "converted" into an NP-compelete problem. Therfore, if we 'find a way to solve an NP-compelete problem in P', we prove that "P=NP".
fun fact: PvsNP itself is an NP-problem

How to prove P!= NP?
>Consider every Alogorithm to every problem that exists in the universe(and ones out of the universe too) and prove that each of them are of different classes(P or NP)
How to prove P=NP?
>Handicap Computers(cheat to show that P-class problems take Non-deterministic Polynomial tie to be solved)
>Feed Larger inputs(again, cheat the classical computers)
>Feed Complex infinite(tending to) inputs (still cheating)
>use distributed systems(to show NP-problems can be solved faster, cheat)
>use Quantum computers(to show NP-problems can be solved faster)

Consider a problem, where you need to determine which is the best move in chess, at a given time.
It is a hard problem as of P by itself. Now consider if the problem was to verify if the given move is the best move in chess. Being an Np-type problem, there is no existing algorithm that can verify even that. These kinds of problems belong to a special class of problems, called as NP-Hard problems.
Mathematicians have spent the recent of their times in re-classifying the problem-complexities.
There are many more classes than there used to be.
Check this out : https://en.wikipedia.org/wiki/List_of_complexity_classes

My presonal takeaway from this:
We will be in the continuous process of finding better algorithms or ways to 'tackle' a problem, to make life easier to humanity.
With the advent of Quantum Computers to the levels of current supercomputers, many of the np-Problems might get solved with a faster way.
We seek to learn from nature. And nature is not in binary; it stores data in Quantum-bits(?). If we manage to crack that, we might not need to consider complexities of current problems, rather just adopt from the nature's ways.
	Before addressing the big questions, we'll get into what it is based on, so everyone can justify the address.
	So let us just look at the world for an instance. The world is filled with questions.

	Now, consider a class of problems, that computers can easily solve, call it 'P'. But 'easy' is not an appreciably quantifiable metric. That's when the study of Algorithmic complexities comes in. We can use the big-Oh 'O' notation to quantify 'easy'.
	Redifining P, it is the class of algorithms(solutions of a problem) which can be solved in polynomial time.
	or P = { solvable problem in polynomial time } (O being quite generous, like O(n^10000) os so)
	eg: finding product of 2 numbers, finding gcd, etc. the essence being, that it is just simpler to work the algorithm.

	Now, consider a set of problems, whose solution has vast parametric dependability, ergo cannot be solved easily. Which means the complexity of the algorithms is so high, that computers might take ages, arriving at optimal solutions.
	Although, provided the solution, it is easy to cross-verify it. eg: given a solved jigsaw puzzle, we can easily verify if it is right; although solving it(from scratch) (or figuring out if it can be solved) will take way too much time (exponential increase of time, with increase in number of pieces). Such problems can be solved, but it cannot be determined polynomially. Should we have a trial-set of values, it is possible to see if it 'provides the right solution' within polynomial time.
	tip: a class of machines can be used to verify the parametric values of an algorithm to obtain a value os true.(biased towards 'yes' (biased towards 'no' => co-NP))
	So redifining, NP = { decision problems solvable in non-deterministic polynomial time }
	[So NP => producing solution is hard, verifying is easy]

	Note: other class of problems in the end.

	One of the examples of an NP problem is 3SAT (sat-datisfiability, 3-literals)
	given a Boolean equation of the form (X1 V X3 V X6) ^ (X2 V X4 V X7) ^ ........
	we need to set each Xi = {0,1}, such that the whole equation = true.
	check: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability
	Simiral problems are Scheduling, Map Coloring, Packing, Puzzles, Protein Folding, Travelling Salesman, CLIQUE.

	On the 20th of may, 2000; The Clay Institute of Mathematics announced $1M as prize amount to anyone solving one of 7 following problems:
	1. Poincare Conjecture(\/) 2. P versus NP problem 3. Navier-Stokes problem 4. Riemann Hypothesis 5. Brich amd Swinnerton-Dyer conjencture 6. Yang-Mills theory 7. Hodge conjecture
	Note: Poincare Conjecture was solved by a Russian Mathematecian, Grigori Perelman in 2003.

	As time went, people discovered some algorithms that solved the problems (which was previously thought to be of NP class), within Polynomial time. This lead to the common question that, 'can every problem(that are currently thought to be of NP) be solved within P?' "Can we discover simpler algorithms to every problems that exists in NP, so as to be solved within P?" "for each NP-type problem, does there exist a P-type algorithm, just as there exists NP-type solution to a P-type problem?" "is P eqaul to NP?" "P=NP?"

	<b>NP-compeleteness<b> This is perhaps the first (and only) step taken toward addressing the big Question.
	People discovered that there existed some NP-type problems, whose core logic was linked to many of the NP-type problems. They found out that any NP-type problem can be converted to form of this problem(reverse is not true). It means that finding a faster way to solve the considred problem eould imply finding a faster way to solve all related NP-type problems. These considred problems are of the class "NP-Compelete".
	Tip: There are several NP-compelete problems. eg: SAT, CLIQUE(https://en.wikipedia.org/wiki/Clique_problem)
	Takeaway being, any NP-type problem can be "converted" into an NP-compelete problem. Therfore, if we 'find a way to solve an NP-compelete problem in P', we prove that "P=NP".
	fun fact: PvsNP itself is an NP-problem

	How to prove P!= NP?
	>Consider every Alogorithm to every problem that exists in the universe(and ones out of the universe too) and prove that each of them are of different classes(P or NP)
	How to prove P=NP?
	>Handicap Computers(cheat to show that P-class problems take Non-deterministic Polynomial tie to be solved)
	>Feed Larger inputs(again, cheat the classical computers)
	>Feed Complex infinite(tending to) inputs (still cheating)
	>use distributed systems(to show NP-problems can be solved faster, cheat)
	>use Quantum computers(to show NP-problems can be solved faster)

	Consider a problem, where you need to determine which is the best move in chess, at a given time.
	It is a hard problem as of P by itself. Now consider if the problem was to verify if the given move is the best move in chess. Being an Np-type problem, there is no existing algorithm that can verify even that. These kinds of problems belong to a special class of problems, called as NP-Hard problems.
	Mathematicians have spent the recent of their times in re-classifying the problem-complexities.
	There are many more classes than there used to be.
	Check this out : https://en.wikipedia.org/wiki/List_of_complexity_classes

	My presonal takeaway from this:
	We will be in the continuous process of finding better algorithms or ways to 'tackle' a problem, to make life easier to humanity.
	With the advent of Quantum Computers to the levels of current supercomputers, many of the np-Problems might get solved with a faster way.
	We seek to learn from nature. And nature is not in binary; it stores data in Quantum-bits(?). If we manage to crack that, we might not need to consider complexities of current problems, rather just adopt from the nature's ways.