Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The P=?NP Poll (2002) [pdf]

cs.umd.edu

Post reply on HN
Print view View original

81–87 of 87 posts

Re: The P=?NP Poll (2002) [pdf]

#81

Post by throwawayaccnt3 »

Nomentatus wrote: post #80

Reference needed: Once upon a time Turing Machines were my thing. But that was decades ago. Now I think I have a result that's interesting, following up on graduate school work I did way back when... but... reading such things as the P=NP prize problem definition I see that at least some terminology in the field has changed, or at least, concepts have been added. (Such as "language", if I remember rightly.) Can someo…

If investigating a specific result, I would recommend Wikipedia, ComplexityZoo and yes, even CSTheory.StackExchange. There are more comprehensive documents, however (re)learning a field may be an overinvestment to test a single idea.

Re: The P=?NP Poll (2002) [pdf]

#82

Post by groovy2shoes »

stratfordfellow wrote: post #34
komali2 wrote: post #27

Earlier quoted context omitted.

Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?

What you're looking at is the theory of computational complexity. Here's a short-ish overview: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/... For a more extensive overview, try this textbook by Michael Sipser (Amazon Affiliate Link if feeling generous: http://amzn.to/2fy9tKZ , Google Books link otherwise: https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introducti... ).

The Sipser book is excellent. It's one of only a handful of textbooks I decided to keep after I graduated from university. And perhaps the only one I kept because of how good it was rather than because the campus bookstore wanted to give me a pittance for it... and I didn't even buy the book until after the semester when I had to return the copy I'd checked out from the library...

I later on picked up the first two editions of Hopcroft & Ullman for $1 each at a used book store. I don't think either edition can really hold a candle to the Sipser book, which is shorter, more thorough, and (imo) easier to understand.

One caveat: it's super-expensive. I'd recommend finding a used copy or even an "international edition" (which will be soft-cover rather than hard-cover, but the content is the same).

Re: The P=?NP Poll (2002) [pdf]

#83

Post by Terr_ »

OJFord wrote: post #47
woliveirajr wrote: post #38

Earlier quoted context omitted.

I love his timing: Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic

> by either 2048 or 4096 It's an odd statement for a mathematician/computer scientist. It's equivalent to "by 4096", surely.

Logically, you don't even need the first clause, since anything solved "by" the first milestone should remain and be solved "by" the second as well :p

Re: The P=?NP Poll (2002) [pdf]

#84

Post by lotsoflumens »

Ar-Curunir wrote: post #69
lotsoflumens wrote: post #6

Earlier quoted context omitted.

>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms. Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the ga…

NP hardness is defined in terms of worst-case hardness, not average case hardness. As long as there exists even one instance that makes your algorithm take non-polynomial amount of time to terminate, P won't be equal to NP.

That's why I'm becoming increasingly skeptical of the usefulness (in the scientific sense) of complexity theory as it's currently laid out. We already know that instances of NP-Hard problems are either easily solvable, in poly-time, or take exponential time, depending on the location of the instance in the problem space.

For example in SAT, the distance of the instance to the critical clause/variable threshold. In subset sum, the density of the instance.

It's not the problem class that matters.

Re: The P=?NP Poll (2002) [pdf]

#85

Post by OJFord »

Terr_ wrote: post #83
OJFord wrote: post #47

Earlier quoted context omitted.

> by either 2048 or 4096 It's an odd statement for a mathematician/computer scientist. It's equivalent to "by 4096", surely.

Logically, you don't even need the first clause, since anything solved "by" the first milestone should remain and be solved "by" the second as well :p

Yes, that's my point.

Re: The P=?NP Poll (2002) [pdf]

#86

Post by Nomentatus »

throwawayaccnt3 wrote: post #81
Nomentatus wrote: post #80

Reference needed: Once upon a time Turing Machines were my thing. But that was decades ago. Now I think I have a result that's interesting, following up on graduate school work I did way back when... but... reading such things as the P=NP prize problem definition I see that at least some terminology in the field has changed, or at least, concepts have been added. (Such as "language", if I remember rightly.) Can someo…

If investigating a specific result, I would recommend Wikipedia, ComplexityZoo and yes, even CSTheory.StackExchange. There are more comprehensive documents, however (re)learning a field may be an overinvestment to test a single idea.

Certainly it's not in Wikipedia, and if Google knows about it; I've probably visited it. A question in CSTheory.StackExchange might work, though.

Re: The P=?NP Poll (2002) [pdf]

#87

Post by throwawayaccnt3 »

Nomentatus wrote: post #86
throwawayaccnt3 wrote: post #81

Earlier quoted context omitted.

If investigating a specific result, I would recommend Wikipedia, ComplexityZoo and yes, even CSTheory.StackExchange. There are more comprehensive documents, however (re)learning a field may be an overinvestment to test a single idea.

Certainly it's not in Wikipedia, and if Google knows about it; I've probably visited it. A question in CSTheory.StackExchange might work, though.

Wikipedia won't have an entry on every specific problem, but it can come in handy if there's a general idea of what to search for. A quick investigation on "language" reveals "Formal Language" and "Model Theory" are relevant topics.
Post reply on HN