Author |
Topic: NP Completeness section? (Read 1688 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
NP Completeness section?
« on: Aug 3rd, 2002, 11:48pm » |
 Quote  Modify
|
I'm considering putting up a new section of interesting NP completeness reduction problems. Those of you with experience with NPC problems should know that they're just like riddles -- often you have to construct clever "gadgets" that allow you to show that two problems are equivalent, and it's often not obvious at all how to go about doing this. What do you guys think of my proposal? I'd also include a crash course on how to show that one problem is equivalent to another, for those with no NPC background.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
 |
Re: NP Completeness section?
« Reply #1 on: Aug 5th, 2002, 11:01am » |
Quote Modify
|
Will,
As per my previous posts, I would prefer all the sections eventually be merged, but I am guessing from you non-responses to my other suggestion msgs that you do not agree. 
Oh well, that's my two cents!
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NP Completeness section?
« Reply #2 on: Aug 5th, 2002, 2:23pm » |
Quote Modify
|
Sorry, I wasn't deliberately not responding, just didn't have the time to get around to it. I checked out some of the other threads and replied to them; as always, thanks for the feedback and being so interested in the site's development.
Indeed, I don't agree with the merge, mostly because I fear the pages will become too unwieldy.
I am interested in what people think of adding NP Complete problems though. They are a rather specialized area of study ... would they not flow well with the spirit of the site?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NP Completeness section?
« Reply #3 on: Aug 7th, 2002, 3:42pm » |
Quote Modify
|
I think they would be fine -- not so different from the CS section, after all. In fact, you could even put them in there.
BTW, random q I'll tag on to this thread so as not to waste too much threadage: How and when do you determine when to add a new puzzle to your list? I've noticed that even when I posted those last five simulataneously they went in half at a time. And similarly with my original e-mail to you. (Not that I mid of course! Just curious; originally I thought you just liked some problems more than others.)
And on a related note: unless you have some other objection, I would recommend you add Frost's patient question and Ollie's answering machine question.
And do you read all the threads btw?
Hm, I think I had more specific comments/suggestions, too, but I'm too beat from work to remember them just now. Oh, for example, I thought maybe you could allow sorting of threads by replies or hits, although I guess that's most likely controlled by yabb...
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: NP Completeness section?
« Reply #4 on: Aug 10th, 2002, 2:02pm » |
Quote Modify
|
Thanks for fixing the tabs in tt mode.
NP-completeness problems are lots of fun =). My favorite NP related problem is:
You've made the breakthrough every theorist dreams of: you've solved P vs NP. Surprisingly enough, you've shown that P=NP, but sadly your proof was non-constructive. Design a poly-time program to solve SAT.
|
| « Last Edit: Aug 10th, 2002, 8:48pm by AlexH » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NP Completeness section?
« Reply #5 on: Aug 10th, 2002, 8:51pm » |
Quote Modify
|
on Aug 7th, 2002, 3:42pm, Eric Yeh wrote:
BTW, random q I'll tag on to this thread so as not to waste too much threadage: How and when do you determine when to add a new puzzle to your list? I've noticed that even when I posted those last five simulataneously they went in half at a time. And similarly with my original e-mail to you. (Not that I mid of course! Just curious; originally I thought you just liked some problems more than others.)
And on a related note: unless you have some other objection, I would recommend you add Frost's patient question and Ollie's answering machine question.
And do you read all the threads btw?
|
|
Well, it's not systematic ... whenever I have some spare time, I look through my e-mail / forum for new riddles, think about them for a tiny bit, and then add to the archive if I like them. My favorite riddles are ones that are unintuitive. Algorithm design problems are also cool. I try not to add riddles that require knowledge outside of the problem statement itself; however, mathematical knowledge is OK to some extent. For instance, someone recently submitted some riddles that require knowing the rules of tennis ... not my cup of tea.
I also try not to add riddles that are ill-defined or too open-ended. So that's why the riddles get added in chunks in sometimes ... I spend a little time thinking about whether the riddle makes sense to me.
Frost's riddles have been added, thanks.
Unfortunately, I don't have time to read all the threads. However, I think I've read a good deal. Very entertaining and educational
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NP Completeness section?
« Reply #6 on: Aug 14th, 2002, 3:46pm » |
Quote Modify
|
Fair enough -- thanks for the explanation!
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NP Completeness section?
« Reply #7 on: Aug 28th, 2002, 6:29pm » |
Quote Modify
|
I decided to add NPC riddles to the CS section; currently there are two: Punchout cards and Steiner tree. More will be added as they come along.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print