Ideas on Complexity Theory P=NP problem

[xfelix]

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:)

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

To 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 thoughts
Well 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?

[runninggee57]

I've also had a little interest in this and read up on some things. The one topic that's confusing to me is that apparently if someone can prove that one problem currently in NP can be solved in polynomial time, then all of the problems in NP can be solved in this time as well.

Does anyone know where this came from? It does simplify the issue down but obviously hasn't made it much easier.

[xfelix]

I read that from a thesis from a professor at some university last year lol. I think it was university of maryland, but my memory is a little fuzzy on this. I had printed the paper out but then i spilt something on it. Basically the idea behind that is the nature of NP problems in general, they can be written using some form of Binary Relations. google P=NP minesweeper problem, It's interesting they build binary circuits out of mine sweeper boards. since all the NP problems have this relation, if you can solve one puzzle in polynomial time, one should be able to solve all the puzzels in polynomial time.

[damncookiemonster]

I'm pretty sure that Sudoku isn't NP. I think that I saw once an algorithm that solves it in O(n^3) or something, given that there is only one possible solution.

NP problem is defined as a problem that you can take another NP problem and make a reduction to it, starting with some well known problem. But that wasn't English was it? This is English:
1. NP problem is a problem that (to our knowledge) can't be solved in polynomial time.
2. You can take any NP problem and solve it using any other NP problem (reduction).
If you find a problem that satisfies one of the conditions and contradicts the other, then you just proved that P=NP.

Most computer science professors don't deal with that question because they believe that P!=NP, and even if someone proves that P=NP, then the reduction would be so complicated it won't really help anyone in terms of time complexity.

Mathematicians, by the way, claim that either N=1 or P=0. That's their way of avoiding it...

[a_ddicted]

Complexity theory is a very interesting field of study in the field of Applied Mathematics-Theoretical Computer Science.
If anyone wants to study about complexity theory i have some books to suggest. I don't post them here because i don't know if it will be considered as an advertise. So if someone wants, you can send me a pm.

[tgoe]

I'm generally against locking/etc necro'd threads if something of value is added. Hurry up and suggest some books...

[LoGiCaL__]

^Agree

[KthProg]

I think I may be coming up with an algorithm that factors numbers in polynomial time.
I also might not be lol.
But I do believe that number factorization is one of the problems considered to be NP, so if I created an algorithm that factored numbers in polynomial time according to the above, I would have proved that P=NP.

-- Tue Feb 26, 2013 11:04 pm --

btw there's a million dollar prize for solving this problem.