P=NP?For those who don't know the P=NP problem, it is a big conjecture of computer science in complexity theory these days. The P stands for set of all Polynomial run-time algorithms and NP stands for set of all Non-polynomial run-time algorithms.
Examples
P = {selection sort, radix sort, binary search, ... , inserting a node in a binary tree}
NP = {solving sudoku, minesweeper problem, traveling sales person, ... , 8 queens problem}
Not completely sure if these sets are finite sets:)
ProblemProve P = NP or P != NP
For the official declaration of problem check the following link
http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdfTo this day no one has been able to prove either or, and is an open important topic of today. It is such an important problem that if anyone can prove this then they will win an award of 1 million dollars!!! Other incentives to solve P=NP.... well if it can be shown that P=NP then encryptions thought to take 20,000 years to crack now suddenly take 2 seconds to crack. This will revolutionize the way we compute data. It is thought that we might be ahead of our time alittle and need to change electrical components making up circuitry.
Anyone here of the memrister that will be coming soon? My thoughtsWell sofar I know since P and NP are both sets then to show that P=NP, one must show that P is a subset of NP and that NP is a subset of P. If anyone can find a way to determine how long an algorithm will take to solve any NP problem then you've shown that NP is a subset of P. If we had a simple bubble sort forexample it runs in O(n^2), which is the max bound of the expected run-time for a data of length n to sort. Well ok now let's say we have a sudoku board a 9X9 board with 9 3X3 grids within. There are 81 total blocks and with some simple combinatorics we get 9^81 maximum number of brute force possible during the algorithm run. we know that 1 <= #comparisons <= 9^81. That's all i'm saying for now unless this thread turns out good. I could be on the wrong direction, but just my thoughts on this problem.
Anyone else think about this problem occasionally here? got any ideas?