9 ms·

P vs. NP

390 points by ikeboy 10y ago

alanh 10y ago
Any survey that mentions Borges in its introductory section is A-OK in my book. Edit This reminds me of an assignment my Discrete Math professor, Dr. Fishel, gave me, which shows how to create (in polynomial time) a Hamiltonian circuit in any undirected graph in which every vertex is of the order ceiling(n/2) where n is the number of vertices in the graph. A C++ implementation is provided. [2007] https://alanhogan.com/asu/hamiltonian-circuit/ https://alanhogan.com/asu/hamiltonian-circuit/
- zeroer 10y ago
  You must be forgetting some important prerequisite to the graph, because there's no circuit on a graph of two vertices and a single edge between them.
  - alanh 10y ago
    n=3 is the minimum. I believe this is in the associated presentation.
cyorir 10y ago
I'll read this if I can afford the time! It would be nice if there were a summary more detailed than the abstract but still short relative to the length of the article (say, 10-pages long?).
- powera 10y ago
  If I had to summarize it from one sentence from the article, I'd go with: "The one prediction I feel confident in making is that the idea of “ironic complexity theory”—i.e., of a profound duality between upper and lower bounds, where the way to prove that there’s no fast algorithm for problem A is to discover fast algorithms for problems B, C, and D—is here to stay."
- idlewords 10y ago
  Just skim it, and read pieces that catch your eye. It's well-organized.
heliophobicdude 10y ago
Abstract: In 1950, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2016, for a broad audience of mathematicians, scientists, and engineers. I offer a personal perspective on what it’s about, why it’s important, why it’s reasonable to conjecture that P≠NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems. The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.
- dilap 10y ago
  The handwritten letters from Nash are awesome. Highly recommend checking them out.
mroll 10y ago
I've read both of his other survey articles linked in the post. Judging by those this will certainly be interesting. Aaronson does a great job tying formal theory to applications and getting across a good mental model for the math he writes about. Looking forward to digging into this one!
gregschlom 10y ago
>...and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithm This is way over my head, but anyone has any insight on that? Sounds intriguing.
- j2kun 10y ago
  There is a large, emerging body of research in which one proves the impossibility of solving problem A by finding an algorithm for solving a different problem B. For Mulmuley et al. (it's been a while since I was in the thick of this) it's finding an algorithm for computing a particular decomposition of a representation[1] having to do with determinants and permanents. This essentially shows the matrix permanent formula can't be written as a determinant of a small matrix (of smaller formulas of the variables), which is the "algebraic" analogue of P vs NP, and which Mulmuley et al. believe will pave a road toward P vs NP. Last I heard there was a serious blow to this program. (edit [3]) For Ryan Williams, it's a more direct approach to separating complexity classes such as ACC (a small circuit class) and NEXP (a large turing machine class), where this[2] is the most amazing explanatory technical document I have seen for almost anything. He also has this program whereby if you can find faster algorithms for boolean satisfiability (SAT)—that is, faster exponential-time algorithms—you get complexity class separations "for free." [1]: https://en.wikipedia.org/wiki/Representation_theory https://en.wikipedia.org/wiki/Representation_theory [2]: https://arxiv.org/abs/1111.1261 https://arxiv.org/abs/1111.1261 [3]: https://arxiv.org/abs/1604.06431 https://arxiv.org/abs/1604.06431
  - deleted 10y ago
    [deleted]
bmh100 10y ago
If you are interested in the implications of P vs. NP, as opposed to a survey of the situation around the problem, check out this excellent essay [1] by Scott Aaronson. He goes into interesting consequences about the nature of quantum computing, simulation of a human mind, and time travel, among other topics. There is also another interesting article [2] by Arkady Bolotin at Ben-Gurion University in Israel, who argues that the lack of macroscopic quantum behavior implies P!=NP. Basically, macroscopic quantum behavior would imply that the universe is computing the solution to a NP-hard problem in violation with currently accepted laws of physics. Also, see this debate between Bolotin and an educated commenter [3]. [1]: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf [pdf] [2]: https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a#.hybznxnd5 https://medium.com/the-physics-arxiv-blog/the-astounding-lin... [3]: https://www.researchgate.net/post/P_NP_and_quantum_nature_of_universe-any_thoughts https://www.researchgate.net/post/P_NP_and_quantum_nature_of...
- ikeboy 10y ago
  >The problem is that the equation says nothing about how large an object needs to be before it obeys Newtonian mechanics rather than the quantum variety. I'm pretty sure this is BS. The linked medium post does nothing to defend the implicit premise that the universe can be computed in a reasonable amount of time by classical computers.
  - frozenport 10y ago
    Indeed it is, interference phenomena have so far scaled up to fairly large many atom structures in rather predictable ways. The real problem for Quantum mechanics starts happening when needing to explain gravity.
    - dlubarov 10y ago
      I think you're talking past the parent, whose point is that our universe's physics may not be polynomial time computable (or computable at all, for that matter).
debt 10y ago
Is there any math addressing how much more quickly NP-hard problems could be computed when time is a flat circle?
- gjm11 10y ago
  Yup, or at least when you have access to a "closed timelike curve" which I think is close enough to what you're asking. See, e.g., this -- which is a transcript of a lecture given by the author of the survey article in the OP. http://www.scottaaronson.com/democritus/lec19.html http://www.scottaaronson.com/democritus/lec19.html With the help of a CTC you can solve any problem in class NP in polynomial time; in fact you can do better and solve anything in PSPACE in polynomial time; and the capabilities of quantum and classical computers are the same. (The last of those is a result due to Scott Aaronson -- author of the survey article in the OP -- and John Watrous.)
nabla9 10y ago
> 6.4 Ironic Complexity Theory TIL
- jonathanstrange 10y ago
  I suppose it has been invented in England (or Denmark).
  - Ar-Curunir 10y ago
    Nah, Stanford.
lisper 10y ago
Do yourself a favor and take the time to read this paper not just to learn about P=?NP but also to see a model of how technical writing ought to be done. Scott Aaronson is truly the Richard Feynman of our day. Not only is he freaking brilliant, but his writing style is accessible, not too mathy, even humorous at times. This made me LOL: "We see a similar “invisible fence” phenomenon in Leslie Valiant’s program of “accidental algorithms” [246]. The latter are polynomial-time algorithms, often for planar graph problems, that exist for certain parameter values but not for others, for reasons that are utterly opaque if one doesn’t understand the strange cancellations that the algorithms exploit. A prototypical result is the following: [Abstruse theorem elided, but it boils down to: there's this weird problem with a parameter k that can be proven to have polynomial-time solutions for some values of k and proven to be NP-hard for other values of k.] Needless to say (because otherwise you would’ve heard!), in not one of these examples have the “P region” and the “NP-complete region” of parameter space been discovered to overlap."
- pron 10y ago
  > to see a model of how technical writing ought to be done Well, this is semi-popular technical writing directed at people who are not theory-of-computation researchers. If all scientific writing would be written like this, then all papers would be at least hundreds of pages long and skip important details. It's absolutely wonderful -- and I think vital -- that a researcher takes the time to do popular writing, but most scientific writing can't be popular. This kind of writing is usually reserved for surveys, like this one. Popular renderings of groundbreaking research also exist in publications like Scientific American, and blog posts by researchers like Aaronson who like (and are good at) communicating their findings in this way, but the important details are often very much research-level and quite impenetrable to all but very specialized researchers.
  - lisper 10y ago
    This isn't popular writing, it's a review. The target audience here is definitely technical, just not specialists.
    - 10y ago
mathgenius 10y ago
His remarks on "geometric complexity theory" are very interesting (starting p80): I like to describe GCT as “the string theory of computer science.” Like string theory, GCT has the aura of an intricate theoretical superstructure from the far future, impatiently being worked on today. Both have attracted interest partly because of “miraculous coincidences” (for string theory, these include anomaly cancellations and the prediction of gravitons; for GCT, exceptional properties of the permanent and determinant, and surprising algorithms to compute the multiplicities of irreps). Both have been described as deep, compelling, and even “the only game in town” (not surprisingly, a claim disputed by the fans of rival ideas!). And like with string theory, there are few parts of modern mathematics not known or believed to be relevant to GCT.
deleted 10y ago
[deleted]
d23 10y ago
A guy at a company I used to work for made a great video on this. Very understandable even without any background on the topic: https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s
DonHopkins 10y ago
My eccentric CS professor had a t-shirt that said "P = NP? I don't know and I don't care."
- gspetr 10y ago
  I saw another amusing one: "P = NP" over a t-shirt depicting that X-Files picture - "I want to believe".

390 points by ikeboy 10y ago

alanh 10y ago

Any survey that mentions Borges in its introductory section is A-OK in my book. Edit This reminds me of an assignment my Discrete Math professor, Dr. Fishel, gave me, which shows how to create (in polynomial time) a Hamiltonian circuit in any undirected graph in which every vertex is of the order ceiling(n/2) where n is the number of vertices in the graph. A C++ implementation is provided. [2007] https://alanhogan.com/asu/hamiltonian-circuit/ https://alanhogan.com/asu/hamiltonian-circuit/

zeroer 10y ago
You must be forgetting some important prerequisite to the graph, because there's no circuit on a graph of two vertices and a single edge between them.
- alanh 10y ago
  n=3 is the minimum. I believe this is in the associated presentation.

cyorir 10y ago

I'll read this if I can afford the time! It would be nice if there were a summary more detailed than the abstract but still short relative to the length of the article (say, 10-pages long?).

powera 10y ago
If I had to summarize it from one sentence from the article, I'd go with: "The one prediction I feel confident in making is that the idea of “ironic complexity theory”—i.e., of a profound duality between upper and lower bounds, where the way to prove that there’s no fast algorithm for problem A is to discover fast algorithms for problems B, C, and D—is here to stay."
idlewords 10y ago
Just skim it, and read pieces that catch your eye. It's well-organized.

heliophobicdude 10y ago

Abstract: In 1950, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2016, for a broad audience of mathematicians, scientists, and engineers. I offer a personal perspective on what it’s about, why it’s important, why it’s reasonable to conjecture that P≠NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems. The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.

dilap 10y ago
The handwritten letters from Nash are awesome. Highly recommend checking them out.

mroll 10y ago

I've read both of his other survey articles linked in the post. Judging by those this will certainly be interesting. Aaronson does a great job tying formal theory to applications and getting across a good mental model for the math he writes about. Looking forward to digging into this one!

gregschlom 10y ago

>...and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithm This is way over my head, but anyone has any insight on that? Sounds intriguing.

j2kun 10y ago
There is a large, emerging body of research in which one proves the impossibility of solving problem A by finding an algorithm for solving a different problem B. For Mulmuley et al. (it's been a while since I was in the thick of this) it's finding an algorithm for computing a particular decomposition of a representation[1] having to do with determinants and permanents. This essentially shows the matrix permanent formula can't be written as a determinant of a small matrix (of smaller formulas of the variables), which is the "algebraic" analogue of P vs NP, and which Mulmuley et al. believe will pave a road toward P vs NP. Last I heard there was a serious blow to this program. (edit [3]) For Ryan Williams, it's a more direct approach to separating complexity classes such as ACC (a small circuit class) and NEXP (a large turing machine class), where this[2] is the most amazing explanatory technical document I have seen for almost anything. He also has this program whereby if you can find faster algorithms for boolean satisfiability (SAT)—that is, faster exponential-time algorithms—you get complexity class separations "for free." [1]: https://en.wikipedia.org/wiki/Representation_theory https://en.wikipedia.org/wiki/Representation_theory [2]: https://arxiv.org/abs/1111.1261 https://arxiv.org/abs/1111.1261 [3]: https://arxiv.org/abs/1604.06431 https://arxiv.org/abs/1604.06431
- deleted 10y ago
  [deleted]

bmh100 10y ago

If you are interested in the implications of P vs. NP, as opposed to a survey of the situation around the problem, check out this excellent essay [1] by Scott Aaronson. He goes into interesting consequences about the nature of quantum computing, simulation of a human mind, and time travel, among other topics. There is also another interesting article [2] by Arkady Bolotin at Ben-Gurion University in Israel, who argues that the lack of macroscopic quantum behavior implies P!=NP. Basically, macroscopic quantum behavior would imply that the universe is computing the solution to a NP-hard problem in violation with currently accepted laws of physics. Also, see this debate between Bolotin and an educated commenter [3]. [1]: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf [pdf] [2]: https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a#.hybznxnd5 https://medium.com/the-physics-arxiv-blog/the-astounding-lin... [3]: https://www.researchgate.net/post/P_NP_and_quantum_nature_of_universe-any_thoughts https://www.researchgate.net/post/P_NP_and_quantum_nature_of...

ikeboy 10y ago
>The problem is that the equation says nothing about how large an object needs to be before it obeys Newtonian mechanics rather than the quantum variety. I'm pretty sure this is BS. The linked medium post does nothing to defend the implicit premise that the universe can be computed in a reasonable amount of time by classical computers.
- frozenport 10y ago
  Indeed it is, interference phenomena have so far scaled up to fairly large many atom structures in rather predictable ways. The real problem for Quantum mechanics starts happening when needing to explain gravity.
  - dlubarov 10y ago
    I think you're talking past the parent, whose point is that our universe's physics may not be polynomial time computable (or computable at all, for that matter).

debt 10y ago

Is there any math addressing how much more quickly NP-hard problems could be computed when time is a flat circle?

gjm11 10y ago
Yup, or at least when you have access to a "closed timelike curve" which I think is close enough to what you're asking. See, e.g., this -- which is a transcript of a lecture given by the author of the survey article in the OP. http://www.scottaaronson.com/democritus/lec19.html http://www.scottaaronson.com/democritus/lec19.html With the help of a CTC you can solve any problem in class NP in polynomial time; in fact you can do better and solve anything in PSPACE in polynomial time; and the capabilities of quantum and classical computers are the same. (The last of those is a result due to Scott Aaronson -- author of the survey article in the OP -- and John Watrous.)

nabla9 10y ago

> 6.4 Ironic Complexity Theory TIL

jonathanstrange 10y ago
I suppose it has been invented in England (or Denmark).
- Ar-Curunir 10y ago
  Nah, Stanford.

lisper 10y ago

Do yourself a favor and take the time to read this paper not just to learn about P=?NP but also to see a model of how technical writing ought to be done. Scott Aaronson is truly the Richard Feynman of our day. Not only is he freaking brilliant, but his writing style is accessible, not too mathy, even humorous at times. This made me LOL: "We see a similar “invisible fence” phenomenon in Leslie Valiant’s program of “accidental algorithms” [246]. The latter are polynomial-time algorithms, often for planar graph problems, that exist for certain parameter values but not for others, for reasons that are utterly opaque if one doesn’t understand the strange cancellations that the algorithms exploit. A prototypical result is the following: [Abstruse theorem elided, but it boils down to: there's this weird problem with a parameter k that can be proven to have polynomial-time solutions for some values of k and proven to be NP-hard for other values of k.] Needless to say (because otherwise you would’ve heard!), in not one of these examples have the “P region” and the “NP-complete region” of parameter space been discovered to overlap."

pron 10y ago
> to see a model of how technical writing ought to be done Well, this is semi-popular technical writing directed at people who are not theory-of-computation researchers. If all scientific writing would be written like this, then all papers would be at least hundreds of pages long and skip important details. It's absolutely wonderful -- and I think vital -- that a researcher takes the time to do popular writing, but most scientific writing can't be popular. This kind of writing is usually reserved for surveys, like this one. Popular renderings of groundbreaking research also exist in publications like Scientific American, and blog posts by researchers like Aaronson who like (and are good at) communicating their findings in this way, but the important details are often very much research-level and quite impenetrable to all but very specialized researchers.
- lisper 10y ago
  This isn't popular writing, it's a review. The target audience here is definitely technical, just not specialists.
  - 10y ago

mathgenius 10y ago

His remarks on "geometric complexity theory" are very interesting (starting p80): I like to describe GCT as “the string theory of computer science.” Like string theory, GCT has the aura of an intricate theoretical superstructure from the far future, impatiently being worked on today. Both have attracted interest partly because of “miraculous coincidences” (for string theory, these include anomaly cancellations and the prediction of gravitons; for GCT, exceptional properties of the permanent and determinant, and surprising algorithms to compute the multiplicities of irreps). Both have been described as deep, compelling, and even “the only game in town” (not surprisingly, a claim disputed by the fans of rival ideas!). And like with string theory, there are few parts of modern mathematics not known or believed to be relevant to GCT.

deleted 10y ago

[deleted]

d23 10y ago

A guy at a company I used to work for made a great video on this. Very understandable even without any background on the topic: https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s

DonHopkins 10y ago

My eccentric CS professor had a t-shirt that said "P = NP? I don't know and I don't care."

gspetr 10y ago
I saw another amusing one: "P = NP" over a t-shirt depicting that X-Files picture - "I want to believe".