wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> suggestions, help, and FAQ >> NP Completeness section?
        
(Message started by: william wu on Aug 3^rd, 2002, 11:48pm)

Title: NP Completeness section?
Post by william wu on Aug 3^rd, 2002, 11:48pm

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.

Title: Re: NP Completeness section?
Post by Eric Yeh on Aug 5^th, 2002, 11:01am

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

Title: Re: NP Completeness section?
Post by william wu on Aug 5^th, 2002, 2:23pm

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?

Title: Re: NP Completeness section?
Post by Eric Yeh on Aug 7^th, 2002, 3:42pm

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

Title: Re: NP Completeness section?
Post by AlexH on Aug 10^th, 2002, 2:02pm

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.

Title: Re: NP Completeness section?
Post by william wu on Aug 10^th, 2002, 8:51pm

on 08/07/02 at 15:42:29, 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 :)

Title: Re: NP Completeness section?
Post by Eric Yeh on Aug 14^th, 2002, 3:46pm

Fair enough -- thanks for the explanation!

Best,
Eric

Title: Re: NP Completeness section?
Post by william wu on Aug 28^th, 2002, 6:29pm

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.