Search

 2 of 2 Prev 1 2
The P versus NP problem
 Posted: 10 May 2013 09:29 PM [ Ignore ]   [ # 16 ]
Sr. Member
Total Posts:  2012
Joined  2007-10-28
alcoan - 08 May 2013 04:29 AM

Could you please tell me if the problem of the 400 students in 50 rooms, the one in the Clay web page, is an NP-C or not?

NP-complete:

That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is at least as “tough” as any other problem in NP.

However:

If any NP-complete problem is in P, then it would follow that P = NP. Unfortunately, many important problems have been shown to be NP-complete, and as of 2013 not a single fast algorithm for any of them is known.

Based on the definition alone it is not obvious that NP-complete problems exist.

Signature

I am, therefore I think.

 Profile

 Posted: 03 December 2013 12:18 PM [ Ignore ]   [ # 17 ]
Jr. Member
Total Posts:  1
Joined  2013-12-03

So I suck at math, and I really don’t know much of anything about anything. But I was intrigued by the complexity of the millennium problems and why so many great minds failed to tackle them. I got especially interested in the P vs NP problem.

I stumbled upon an example of a problem that is theoretically in NP for a computer but seems to be in P for us (to my understanding).

A night in a bar

Do you know these music recognition apps?  They record a piece of music and then produce a digital footprint. Then the program proceeds to compare the digital footprint to a database. In theory this problem should be in NP as the computer has to search through the database to get the answer (in my understanding).

So I was in a bar last night with a friend and this piece of music was playing, I liked it and I wanted to know what the title of the song was, so I proceeded to take out my phone and use some app to figure it out. Before I could even take out my phone my friend told me “don’t bother, it’s called I’m too sexy by Right said Fred”

So then it occurred to me that he didn’t need to search to know that. And while you might say that this is a bad example because our brain is simply a really fast computer (sort of), or that he might have thought about the song since it started to play. Still, our brain (in my understanding) uses a different mechanism to produce an answer. I think that once we listen to a piece of music, then neurones start to fire in a pattern that was produced when we first heard the piece, leading to recognition. So you might say that the answer sort of presents itself, that instead of having to search for it, the answer sort of lights up and embraces the question.

Clique problem

So apparently all problems in NP can be converted to a clique problem. The clique problem consists of a series of connected nodes where you want to know what the largest clique is. A clique is a series of nodes all connected to one another.

Can we not solve the clique problem by using an intrinsic property that we know the answer has, which is that it has the highest number of nodes all connected to one another. Can we not use this to make the answer present itself? Perhaps by giving each node a synergistic property that expresses itself in an exponential manner, but only when it participates in a clique. In this case, the largest clique would produce the highest number. It would perhaps, light up.

Disclaimer

I might be completely in over my head here. But I simply thought that it could do no harm to throw some ideas out there.

 Profile

 Posted: 04 December 2013 04:14 PM [ Ignore ]   [ # 18 ]
Sr. Member
Total Posts:  1635
Joined  2010-04-22
Blockbuster - 03 December 2013 12:18 PM

A night in a bar

Do you know these music recognition apps?  They record a piece of music and then produce a digital footprint. Then the program proceeds to compare the digital footprint to a database. In theory this problem should be in NP as the computer has to search through the database to get the answer (in my understanding).

So I was in a bar last night with a friend and this piece of music was playing, I liked it and I wanted to know what the title of the song was, so I proceeded to take out my phone and use some app to figure it out. Before I could even take out my phone my friend told me “don’t bother, it’s called I’m too sexy by Right said Fred”

So then it occurred to me that he didn’t need to search to know that. And while you might say that this is a bad example because our brain is simply a really fast computer (sort of), or that he might have thought about the song since it started to play. Still, our brain (in my understanding) uses a different mechanism to produce an answer. I think that once we listen to a piece of music, then neurones start to fire in a pattern that was produced when we first heard the piece, leading to recognition. So you might say that the answer sort of presents itself, that instead of having to search for it, the answer sort of lights up and embraces the question.

I’m not quite sure that this is exactly a P vs NP problem. A computer can search through a large database of songs and pick one that best matches, but to be absolutely sure that the song is the same one? I don’t think that computer algorithms are capable of that yet. Even with a 99% degree of accuracy, that is not a proof. Remember, with song recognition apps, it should recognize a song which is the same song but a different recording, so that the binary representation of the song is different.

Of course, part of that problem lies in what constitutes a “song.” The definition may be a bit too vague to allow 100% accuracy of identification. For example, what recording of “Old Man River” is the “real” recording? http://en.wikipedia.org/wiki/Ol’_Man_River#Various_versions

But concerning the brain and music, most people don’t realize just how fantastic our brains are at interpreting sound. Just go and try to look at a waveform version of someone singing “Row Row Row Your Boat” and try to make sense of it. Our eye’s can’t - not really, yet our ears draw enormous information from it. Such things as speech recognition software and music identification software really are amazing accomplishments.

Signature

“All musicians are subconsciously mathematicians.”

- Thelonious Monk

 Profile

 2 of 2 Prev 1 2