Ideas on Complexity Theory P=NP problem

Mathematics and Science; the subtle and ubiquitous arts

Ideas on Complexity Theory P=NP problem

Post by xfelix on Wed Dec 16, 2009 2:03 am
([msg=31429]see Ideas on Complexity Theory P=NP problem[/msg])

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?
xfelix
Experienced User
Experienced User
 
Posts: 71
Joined: Fri Nov 27, 2009 7:40 pm
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by runninggee57 on Fri Dec 18, 2009 5:58 pm
([msg=31581]see Re: Ideas on Complexity Theory P=NP problem[/msg])

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.
runninggee57
New User
New User
 
Posts: 9
Joined: Fri Dec 11, 2009 7:27 pm
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by xfelix on Fri Dec 18, 2009 11:18 pm
([msg=31586]see Re: Ideas on Complexity Theory P=NP problem[/msg])

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. 8-)
xfelix
Experienced User
Experienced User
 
Posts: 71
Joined: Fri Nov 27, 2009 7:40 pm
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by damncookiemonster on Tue May 25, 2010 5:02 pm
([msg=39064]see Re: Ideas on Complexity Theory P=NP problem[/msg])

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...
damncookiemonster
New User
New User
 
Posts: 3
Joined: Sat May 22, 2010 7:51 am
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by a_ddicted on Thu Jan 19, 2012 9:21 am
([msg=63769]see Re: Ideas on Complexity Theory P=NP problem[/msg])

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.
a_ddicted
New User
New User
 
Posts: 3
Joined: Sun Apr 26, 2009 12:47 pm
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by tgoe on Fri Jan 20, 2012 1:30 am
([msg=63780]see Re: Ideas on Complexity Theory P=NP problem[/msg])

I'm generally against locking/etc necro'd threads if something of value is added. Hurry up and suggest some books...
User avatar
tgoe
Contributor
Contributor
 
Posts: 664
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by LoGiCaL__ on Fri Jan 20, 2012 10:15 am
([msg=63792]see Re: Ideas on Complexity Theory P=NP problem[/msg])

^Agree
User avatar
LoGiCaL__
Addict
Addict
 
Posts: 1063
Joined: Sun May 30, 2010 12:33 pm
Blog: View Blog (0)


Re: Ideas on Complexity Theory P=NP problem

Post by KthProg on Tue Feb 26, 2013 8:58 pm
([msg=74195]see Re: Ideas on Complexity Theory P=NP problem[/msg])

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.
User avatar
KthProg
Poster
Poster
 
Posts: 219
Joined: Wed Jan 23, 2013 7:06 pm
Blog: View Blog (0)



Return to Math & Science

Who is online

Users browsing this forum: No registered users and 0 guests