P = NP?

Started by Blizzard, January 03, 2016, 12:18:13 pm

Previous topic - Next topic

Blizzard

January 03, 2016, 12:18:13 pm Last Edit: January 03, 2016, 12:25:42 pm by Blizzard
Sooooo... Anybody ever tried tackling this problem? It's one of the 7 Millennium Prizes of $1,000,000 at Clay Mathematics Institute. I researched it a bit and the first major problem is that you have to make an official publication in a major science journal to even be considered and your proof has to gain "general acceptance" within 2 years. Well, it's a really difficult proof so I'm not that surprised.

Now, they have worked things out in a pretty detailed manner. I haven't dived into it too much, but I noticed that nobody tried simply equating a generalized polynomial function with an exponential and the deriving the shit out of it until it was obvious that they aren't the same and never can be the same. If nothing else, this is another massive indicator that P != NP.

EDIT: Something I noticed is that they are geared towards hardcore logic with postulates and shit for the proofs.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

winkio

Having taken a graduate level logic course, I am quite confident that nobody here is going to come up with anything remotely close to a solution to P = NP.  It's a problem that seems simple at first, but the more you learn about it, the harder it becomes.  Feel free to discuss it I guess, but you aren't really going to appreciate why it's such a difficult and important problem without doing a lot of heavy reading.

Blizzard

I've had an undergraduate AI class where we did some logic so I'm aware that there's no way anybody here's gonna solve it. xD I just wanted to discuss it a bit.

There was an attempt by some guy (can't remember that name, too lazy to google) who tried a few years ago, but the scientific community found many mistakes in his 100-pages paper. I didn't research it much, but apparently he tried to take NP-complete problems and try to solve them using P-algorithms. Many called the attempt initially interesting since it was thinking somewhat out of the box. I think that more out of the box thinking could help move towards an actual solution. I understand the value of formal proof, but because of a too narrow perspective they might be missing something obvious right in front of them.

As for it getting increasingly more complicated the more you dig, I agree. I was reading about the "party problem" and I thought I figured out a way how to do it in polynomial time. But then I read somewhere that if "k is n/2", you basically get x^n/2 checks you have to perform and the problem finally becomes exponential. This made me understand better why it's so difficult to find a proof since it seems that at some point things keep switching back and forth like this. Same with the clique problem and if you have a n and k as input or not. It's nuts.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.