Author Topic: P = NP?  (Read 470 times)

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19913
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
P = NP?
« on: January 03, 2016, 07:18:13 PM »
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.
« Last Edit: January 03, 2016, 07:25:42 PM by Blizzard »
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


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

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

Offline winkio

  • Epiq
  • Administrator
  • Guardian of Chaos
  • *****
  • Posts: 4506
  • LV: 199
  • Gender: Male
  • I am lying.
    • View Profile
Re: P = NP?
« Reply #1 on: January 03, 2016, 07:41:06 PM »
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.

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19913
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: P = NP?
« Reply #2 on: January 03, 2016, 08:27:57 PM »
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      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


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

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