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

61–70 of 87 posts

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

#61

Post by sjclemmy »

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... ).

I bought Sipser for this very purpose. I found it very difficult without being able to discuss it with anyone to clarify my understanding of the ideas. I would love to work through it, but would need a CS tutor to help me... any takers? ;)

Edit: to be honest it's the maths notation that is a big barrier for me. Until one can read it relatively fluently it's very hard to translate the ideas into a meaningful mental model .

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

#62

Post by SilasX »

nialv7 wrote: post #57
SilasX wrote: post #37

Earlier quoted context omitted.

What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each problem corresponds to an oracle for that problem?

You can choose a random oracle by choose a language by random. Here a language means a set of strings.

Can you explain that further? A random oracle is a random set of strings...?

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

#63

Post by austinl »

komali2 wrote: post #27
adilparvez wrote: post #14

A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…

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

This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science).

Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?"

https://www.youtube.com/watch?v=YX40hbAHx3s

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

#64

Post by deathgrindfreak »

komali2 wrote: post #27
adilparvez wrote: post #14

A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…

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

I'd start with an algorithms course, then progress deeper into Complexity theory. Perhaps a bit of discrete mathematics depending on your background.

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

#65

Post by 3pt14159 »

adilparvez wrote: post #14

A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…

What's the probability of recurrence in 4d or 5d? How does one calculate it?

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

#66

Post by tromp »

SilasX wrote: post #62
nialv7 wrote: post #57

Earlier quoted context omitted.

You can choose a random oracle by choose a language by random. Here a language means a set of strings.

Can you explain that further? A random oracle is a random set of strings...?

Flip a coin for each string to decide its membership in the language.

In other words, let the characteristic sequence of the language be an infinite random binary string.

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

#67

Post by SilasX »

tromp wrote: post #66
SilasX wrote: post #62

Earlier quoted context omitted.

Can you explain that further? A random oracle is a random set of strings...?

Flip a coin for each string to decide its membership in the language. In other words, let the characteristic sequence of the language be an infinite random binary string.

So, a language is a mapping from strings to 1/0? And an oracle is a language?

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

#69

Post by Ar-Curunir »

lotsoflumens wrote: post #6
justifier wrote: post #4

Richard Karp: (Berkeley, unsure, P!=NP) 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. I believe that the traditional proof techniques will not suffice. Something entirely novel will be required. My hunch is that the problem will be solved by a young res…

>> 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.

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

#70

Post by deckar01 »

komali2 wrote: post #27
adilparvez wrote: post #14

A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…

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

"Meta Math!: The Quest for Omega" by Gregory Chaitin [0] was my introduction to the theory of computability [1]. I found it enjoyable and approachable.

[0] https://books.google.com/books?id=Z6FJbwggW1sC

[1] https://en.m.wikipedia.org/wiki/Computability_theory

Post reply on HN