6 ms·

As an ex-physicist (quantum physics, now - data science), I am still puzzled why computer scientist consider computational complexity something metaphysical. Or

by stared 10y ago

As an ex-physicist (quantum physics, now - data science), I am still puzzled why computer scientist consider computational complexity something metaphysical. Or even worse - a rule which universe should care about; look up considerations of non-local boxes and computational complexity (a generalization of quantum correlations; see Popescu-Rohrlich box). First, even the CS's nightmare (where P=NP) may mean little practical difference (e.g. the simplest 'NP' takes O(n^1000)). Second, for many problems even O(n^2) is too much (think of big data problems). (Also, given that computation requires physical resources, you cannot scale it arbitrarily.) So even in P the actual exponent matters a lot. One interesting, physical case is the spontaneous emission of a photon from an excited atom. It looks like an exponential decay, but the theory shows that the decay have to be polynomial (I don't remember it's power, if more like 1/t^3 or 1/t^6, but not too high). Up to my knowledge, we haven't detected the polynomial tail (because when it is, the probabilities are so low). So, is there a physical effect that cares about computational complexity? Or a phenomenon in which it matters that we can simulate it in "only" O(n^100), not O(2^n)?

amelius 10y ago
> As an ex-physicist (quantum physics, now - data science), I am still puzzled why computer scientist consider computational complexity something metaphysical. Please don't generalize one or a few computer scientists to the whole group. By the way, a similar thing can be said for the halting problem. We may not be able to prove mechanically whether any program halts, but if we can do it for any program appearing in practice, that may be good enough. Still the proof is of immense theoretical value.
- stared 10y ago
  > Please don't generalize one or a few computer scientists to the whole group. s/computer scientist/some theoretical computer scientists (You are right that I missed a quantifier; this regex would also fix a typo.) > Still the proof is of immense theoretical value. I enjoy mathematics, also in its pure form. Sure, there are many things nice, valuable and beautiful. Some are of practical use. Yet, misusing it is a problem. Some otherwise great minds (like Roger Penrose) make some questionable claims about consciousness based on unjustified implications for the real world.
- eru 10y ago
  > We may not be able to prove mechanically whether any program halts, but if we can do it for any program appearing in practice, that may be good enough. Alas, we can't even do that. Eg I have a simple program that systematically looks for a counterexample to Fermat's Last Theorem, and halts if it finds one. We know now that this simple and comparatively natural program will never halt. But the proof is crazy.
johncolanduoni 10y ago
> First, even the CS's nightmare (where P=NP) may mean little practical difference (e.g. the simplest 'NP' takes O(n^1000)). Sure, it may. But there are precious few examples in the wild where we're dealing with crazy powers like that. I think the bigger (but still quite small) failure in P's ability to measure "ease" of computation is that it only considers the worst case. A good example is graph isomorphism. There was recently a development of a quasipolynomial algorithm for graph isomorphism, which had the best bound we've found for the problem yet. However, with our existing algorithms it was extremely difficult to find examples where they didn't run in polynomial time, even when actively looking for them. But again, this is the exception, not the rule. > Second, for many problems even O(n^2) is too much (think of big data problems). (Also, given that computation requires physical resources, you cannot scale it arbitrarily.) So even in P the actual exponent matters a lot. Very true, but TCS spends a lot of time developing new algorithms to shrink exponents as well. A lot of the methods and skills needed for making better algorithms to get problems into P also apply to moving them around within P. And many of the same tactics for trying to figure out exactly how P and NP fit together apply to trying to figure out the same for P and BQP. Since you have a background in quantum physics and (I assume) care about that field, are you aware that quite a bit of the TCS community works on quantum problems? There have been plenty of results that stand to be very physically relevant. Some good examples are the recent (quite rapid) progress in analyzing symmetric cryptography schemes' vulnerability to attacks by a quantum computers[1]. Interestingly, many are starting from the same jumping off that asymmetric attacks did; namely Simon's algorithm (an important stepping stone towards Shor's algorithm). [1]: https://arxiv.org/abs/1602.05973 https://arxiv.org/abs/1602.05973
- stared 10y ago
  Don't take me wrong - TCS is an important discipline, with both interesting practical and theoretical results. The only thing I am criticizing here is the _metaphysical_ implications of computational complexity classes (and also, jargon which is misleading for not TCS people - e.g. O(n^100) s not "efficient" or "fast"). Furthermore, as you pointed, some problems have practical solutions which usually work efficiently, even if not always or give approximate, but still - useful, solution. > There have been plenty of results that stand to be very physically relevant What I meant was not "can be applied to physical systems" (I agree!), but "is a foundation for physical laws" (I am highly skeptical and I am yet to see an example). (Though, to be honest, I was more in quantum info that quantum computing; and right now I am more into... quantum JavaScript: http://quantumgame.io/ http://quantumgame.io/)
gone35 10y ago
So, is there a physical effect that cares about computational complexity? Or a phenomenon in which it matters that we can simulate it in "only" O(n^100), not O(2^n)? Firewalls[1,2], for starters. [1] http://arxiv.org/abs/1301.4504v4 http://arxiv.org/abs/1301.4504v4 [2] http://arxiv.org/abs/1402.5674 http://arxiv.org/abs/1402.5674
- stared 10y ago
  Thanks! Any summary? (I admit, GRT is not something I am deep into.)
  - gone35 10y ago
    See e.g.: http://online.kitp.ucsb.edu/online/fuzzorfire_m13/aaronson/ http://online.kitp.ucsb.edu/online/fuzzorfire_m13/aaronson/ http://www.scottaaronson.com/talks/hawking.ppt http://www.scottaaronson.com/talks/hawking.ppt
todd8 10y ago
Interestingly, Knuth believes P=NP. See his interview, in particular his answer to question 17: http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m...
im3w1l 10y ago
"The universe believes in encryption." - Assange Most cryptography rests on open problems so I don't think the question is settled yet. In either case, the answer is of immense importance.
chriswarbo 10y ago
> I am still puzzled why computer scientist consider computational complexity something metaphysical. In what sense do you mean "metaphysical"? Personally, I would say computational complexity is both "physical", in the sense that it gives fundamental limits to what can/cannot be done in the physical world using some amount of resources (say, anything obeying Blum's axioms). I would say it's also "metaphysical", in the sense that those limits are derived purely mathematically, and are "imposed on" the physical world; rather than, for example, by observing the physical world and imposing consistency with those observations on some mathematical model. I think of these computational "laws of nature" in a similar way to the "law of nature" that e^(i*pi) + 1 = 0. In other words, we can imagine (AKA develop a consistent mathematical model of) a world operating by Newtonian physics; we can do the same for a world operating by special or general relativity; and for the standard model; we can do it for worlds with N dimensions; with Euclidean, hyperbolic or spherical geometry; and so on. All of these "make sense", in a self-consistent way, and it's up to physicists to figure out which of those models best describes our physical world. On the other hand, there don't seem to be self-consistent models of universal systems which can solve their own halting problem, or models which don't posess the hierarchical complexity classes we've found (although, of course, the machine models may differ, we may introduce hierarchies of halting oracles, etc.). In that sense, these seem to be "laws of nature" which are intrinsic to our models, by virtue of their mathematical definition, rather than being imposed from the outside in order to agree with observations.
ProfChronos 10y ago
The section about closed timelike curves is, I think, a good example of why computational complexity has metaphysical consequences but struggles to bridge the two - see what Aaronson writes about the "grandfather paradox".
nabla9 10y ago
>So, is there a physical effect that cares about computational complexity? The No-SuperSearch Postulate (there is no physical means to solve NP-complete problems in polynomial time) is not purely mathematical conjecture. It's also a claim about the laws of physics. The postulate includes P != NP as a special case, but it is stronger. If you assume that the postulate is true, you can use it to explain things like why quantum mechanics is linear, why adiabatic systems have small spectral gaps, why timeline curves don't exist, black hole information paradox, impossibility of relativity computers, why QM-amplitudes are not directly observable. The question of how much physics you could derive from No-super-search postulate is interesting.
- stared 10y ago
  And it is assumption I find... strange. If it really works, it would be interesting. QM is linear for many other reasons (the simplest related to not being able communicate faster than light); smallness of spectral gaps is AFAIK a conjuncture. And in general, playing with causality will bring many other problems.
  - Cybiote 10y ago
    The principle is essentially a recognition that, if there were no constraints on energy or other physical limits, then many problems in NP or harder would be tractable. This bridge might be two-way, so we may start from complexity and ask: what bounds might we expect in physics since without, this problem would be tractable? One relevant example is protein folding, which is NP-complete. Why then have we not found arrangements such that protein conformations are solutions to NP-complete problems? It's reasonable to postulate that nature does not actually solve NP-complete problems and that almost all carriers of problematic instances died off (not completely, since prions exist after all). If this is the case then we can make a prediction that there exists some polynomial time algorithm able to predict conformations of biologically encountered instances in reasonable time to high accuracy and that a program search such as deep learning will one day find this algorithm given sufficient data. That would be a huge deal. +++ The following links argue more or less that from a bayesian perspective, a prior weighted heavily on smaller exponents for the case P=NP, is more reasonable given the examples and rarity of realistically intractable polynomial time algorithms (and how quickly they seem to fall to reasonable with focused attention). Paragraph 3 in http://www.scottaaronson.com/democritus/lec6.html http://www.scottaaronson.com/democritus/lec6.html Argument 1 in https://windowsontheory.org/2013/05/06/reasons-to-care-in-honor-of-scott-aaronson/ https://windowsontheory.org/2013/05/06/reasons-to-care-in-ho...
pdonis 10y ago
> the theory shows that the decay have to be polynomial I thought this was the other way around: the theory predicts exact exponential decay, but experiments aren't entirely clear that that is always the case. Depending on which textbook or paper you read, some say the deviations from exact exponential decay are just experimental error, while others say they are evidence of additional effects that the exponential decay law does not account for.
- stared 10y ago
  It's clearly not that way you say. From quantum field theory, you get polynomial decay and it's quite fundamental (related to causality, holomorphic functions (Kramers–Kronig relations)) and if it were not working, a lot of physics would need rewriting. EDIT: I remember it from a lecture, many years ago. Some googling brings me to this thread with links to papers: http://physics.stackexchange.com/questions/7008/long-time-deviations-from-exponential-decay-in-radioactivity http://physics.stackexchange.com/questions/7008/long-time-de...
  - pdonis 10y ago
    > From quantum field theory, you get polynomial decay I think you're oversimplifying, although I agree that I was also oversimplifying when I said that the theory predicts exact exponential decay. What I get from that stack exchange thread and the linked papers is this: in an idealized (and not physically possible for a real system) model in which every individual decay is statistically independent from every other and in which all of the quantum states that are possible end points of the decay are unoccupied, the theory predicts exact exponential decay. But in real physical systems, neither of those conditions is exactly true. Individual members of an ensemble of decaying quantum systems (such as radioactive atoms in a sample) interact with each other (either directly or indirectly via states in the environment), so their decays are not completely independent; and any real decaying system has an external environment which includes some occupied "target" quantum states. When these effects are taken into account, the theory predicts a decay law which is often called "power law" but which I would describe as more of a "truncated exponential": it replaces an infinite series of power law terms (the exact exponential) with a finite number of them. The actual measured decay law in a given experiment will depend on how much the experiment probes the portion of the state space where the above effects are significant (for example, a decay law measured over a very long time can deviate measurably from exponential where a measurement over a shorter time would not).
stared 10y ago
Wow, I got >=3 downvotes. Is the knowledge about non-exponential spontaneous emission so obvious?
- eru 10y ago
  Alas, please disregard early downvotes.
jgeada 10y ago
Well, there is the Landauer's principle (which is related to Maxwell's daemon): there is a physical lower limit to the cost of computations. https://en.wikipedia.org/wiki/Landauer%27s_principle https://en.wikipedia.org/wiki/Landauer%27s_principle So yes, there is a physical cost to non-reversible computation.
- kanzure 10y ago
  see also: "Ultimate physical limits to computation" http://arxiv.org/pdf/quant-ph/9908043v3.pdf http://arxiv.org/pdf/quant-ph/9908043v3.pdf "Limits on fundamental limits to computation" http://arxiv.org/pdf/1408.3821v2 http://arxiv.org/pdf/1408.3821v2 "The physics of information processing superobjects: daily life among the Jupiter brains" http://diyhpl.us/~bryan/papers2/The%20physics%20of%20information%20processing%20superobjects%20-%20Anders%20Sandberg%20-%201999.pdf http://diyhpl.us/~bryan/papers2/The%20physics%20of%20informa...
mmalone 10y ago
Personally, I consider it metaphysical because it says something about provability (since, deep down, proofs and programs are the same thing). Truth beyond proof (or at least beyond what's feasible to prove) is bizarre and mysterious. Metaphysics (and physics) is concerned with uncovering the fundamental truths of the universe. Computational complexity indicates this may be unachievable.
Natanael_L 10y ago
Looks like this is extremely relevant - the Halting problem and Turing completeness applied to quantum physics: http://phys.org/news/2015-12-quantum-physics-problem-unsolvable-godel.html http://phys.org/news/2015-12-quantum-physics-problem-unsolva... http://www.nature.com/nature/journal/v528/n7581/full/nature16059.html http://www.nature.com/nature/journal/v528/n7581/full/nature1...

by stared 10y ago

amelius 10y ago

> As an ex-physicist (quantum physics, now - data science), I am still puzzled why computer scientist consider computational complexity something metaphysical. Please don't generalize one or a few computer scientists to the whole group. By the way, a similar thing can be said for the halting problem. We may not be able to prove mechanically whether any program halts, but if we can do it for any program appearing in practice, that may be good enough. Still the proof is of immense theoretical value.

stared 10y ago
> Please don't generalize one or a few computer scientists to the whole group. s/computer scientist/some theoretical computer scientists (You are right that I missed a quantifier; this regex would also fix a typo.) > Still the proof is of immense theoretical value. I enjoy mathematics, also in its pure form. Sure, there are many things nice, valuable and beautiful. Some are of practical use. Yet, misusing it is a problem. Some otherwise great minds (like Roger Penrose) make some questionable claims about consciousness based on unjustified implications for the real world.
eru 10y ago
> We may not be able to prove mechanically whether any program halts, but if we can do it for any program appearing in practice, that may be good enough. Alas, we can't even do that. Eg I have a simple program that systematically looks for a counterexample to Fermat's Last Theorem, and halts if it finds one. We know now that this simple and comparatively natural program will never halt. But the proof is crazy.

johncolanduoni 10y ago

> First, even the CS's nightmare (where P=NP) may mean little practical difference (e.g. the simplest 'NP' takes O(n^1000)). Sure, it may. But there are precious few examples in the wild where we're dealing with crazy powers like that. I think the bigger (but still quite small) failure in P's ability to measure "ease" of computation is that it only considers the worst case. A good example is graph isomorphism. There was recently a development of a quasipolynomial algorithm for graph isomorphism, which had the best bound we've found for the problem yet. However, with our existing algorithms it was extremely difficult to find examples where they didn't run in polynomial time, even when actively looking for them. But again, this is the exception, not the rule. > Second, for many problems even O(n^2) is too much (think of big data problems). (Also, given that computation requires physical resources, you cannot scale it arbitrarily.) So even in P the actual exponent matters a lot. Very true, but TCS spends a lot of time developing new algorithms to shrink exponents as well. A lot of the methods and skills needed for making better algorithms to get problems into P also apply to moving them around within P. And many of the same tactics for trying to figure out exactly how P and NP fit together apply to trying to figure out the same for P and BQP. Since you have a background in quantum physics and (I assume) care about that field, are you aware that quite a bit of the TCS community works on quantum problems? There have been plenty of results that stand to be very physically relevant. Some good examples are the recent (quite rapid) progress in analyzing symmetric cryptography schemes' vulnerability to attacks by a quantum computers[1]. Interestingly, many are starting from the same jumping off that asymmetric attacks did; namely Simon's algorithm (an important stepping stone towards Shor's algorithm). [1]: https://arxiv.org/abs/1602.05973 https://arxiv.org/abs/1602.05973

stared 10y ago
Don't take me wrong - TCS is an important discipline, with both interesting practical and theoretical results. The only thing I am criticizing here is the _metaphysical_ implications of computational complexity classes (and also, jargon which is misleading for not TCS people - e.g. O(n^100) s not "efficient" or "fast"). Furthermore, as you pointed, some problems have practical solutions which usually work efficiently, even if not always or give approximate, but still - useful, solution. > There have been plenty of results that stand to be very physically relevant What I meant was not "can be applied to physical systems" (I agree!), but "is a foundation for physical laws" (I am highly skeptical and I am yet to see an example). (Though, to be honest, I was more in quantum info that quantum computing; and right now I am more into... quantum JavaScript: http://quantumgame.io/ http://quantumgame.io/)

gone35 10y ago

So, is there a physical effect that cares about computational complexity? Or a phenomenon in which it matters that we can simulate it in "only" O(n^100), not O(2^n)? Firewalls[1,2], for starters. [1] http://arxiv.org/abs/1301.4504v4 http://arxiv.org/abs/1301.4504v4 [2] http://arxiv.org/abs/1402.5674 http://arxiv.org/abs/1402.5674

stared 10y ago
Thanks! Any summary? (I admit, GRT is not something I am deep into.)
- gone35 10y ago
  See e.g.: http://online.kitp.ucsb.edu/online/fuzzorfire_m13/aaronson/ http://online.kitp.ucsb.edu/online/fuzzorfire_m13/aaronson/ http://www.scottaaronson.com/talks/hawking.ppt http://www.scottaaronson.com/talks/hawking.ppt

todd8 10y ago

Interestingly, Knuth believes P=NP. See his interview, in particular his answer to question 17: http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m...

im3w1l 10y ago

"The universe believes in encryption." - Assange Most cryptography rests on open problems so I don't think the question is settled yet. In either case, the answer is of immense importance.

chriswarbo 10y ago

> I am still puzzled why computer scientist consider computational complexity something metaphysical. In what sense do you mean "metaphysical"? Personally, I would say computational complexity is both "physical", in the sense that it gives fundamental limits to what can/cannot be done in the physical world using some amount of resources (say, anything obeying Blum's axioms). I would say it's also "metaphysical", in the sense that those limits are derived purely mathematically, and are "imposed on" the physical world; rather than, for example, by observing the physical world and imposing consistency with those observations on some mathematical model. I think of these computational "laws of nature" in a similar way to the "law of nature" that e^(i*pi) + 1 = 0. In other words, we can imagine (AKA develop a consistent mathematical model of) a world operating by Newtonian physics; we can do the same for a world operating by special or general relativity; and for the standard model; we can do it for worlds with N dimensions; with Euclidean, hyperbolic or spherical geometry; and so on. All of these "make sense", in a self-consistent way, and it's up to physicists to figure out which of those models best describes our physical world. On the other hand, there don't seem to be self-consistent models of universal systems which can solve their own halting problem, or models which don't posess the hierarchical complexity classes we've found (although, of course, the machine models may differ, we may introduce hierarchies of halting oracles, etc.). In that sense, these seem to be "laws of nature" which are intrinsic to our models, by virtue of their mathematical definition, rather than being imposed from the outside in order to agree with observations.

ProfChronos 10y ago

The section about closed timelike curves is, I think, a good example of why computational complexity has metaphysical consequences but struggles to bridge the two - see what Aaronson writes about the "grandfather paradox".

nabla9 10y ago

>So, is there a physical effect that cares about computational complexity? The No-SuperSearch Postulate (there is no physical means to solve NP-complete problems in polynomial time) is not purely mathematical conjecture. It's also a claim about the laws of physics. The postulate includes P != NP as a special case, but it is stronger. If you assume that the postulate is true, you can use it to explain things like why quantum mechanics is linear, why adiabatic systems have small spectral gaps, why timeline curves don't exist, black hole information paradox, impossibility of relativity computers, why QM-amplitudes are not directly observable. The question of how much physics you could derive from No-super-search postulate is interesting.

stared 10y ago
And it is assumption I find... strange. If it really works, it would be interesting. QM is linear for many other reasons (the simplest related to not being able communicate faster than light); smallness of spectral gaps is AFAIK a conjuncture. And in general, playing with causality will bring many other problems.
- Cybiote 10y ago
  The principle is essentially a recognition that, if there were no constraints on energy or other physical limits, then many problems in NP or harder would be tractable. This bridge might be two-way, so we may start from complexity and ask: what bounds might we expect in physics since without, this problem would be tractable? One relevant example is protein folding, which is NP-complete. Why then have we not found arrangements such that protein conformations are solutions to NP-complete problems? It's reasonable to postulate that nature does not actually solve NP-complete problems and that almost all carriers of problematic instances died off (not completely, since prions exist after all). If this is the case then we can make a prediction that there exists some polynomial time algorithm able to predict conformations of biologically encountered instances in reasonable time to high accuracy and that a program search such as deep learning will one day find this algorithm given sufficient data. That would be a huge deal. +++ The following links argue more or less that from a bayesian perspective, a prior weighted heavily on smaller exponents for the case P=NP, is more reasonable given the examples and rarity of realistically intractable polynomial time algorithms (and how quickly they seem to fall to reasonable with focused attention). Paragraph 3 in http://www.scottaaronson.com/democritus/lec6.html http://www.scottaaronson.com/democritus/lec6.html Argument 1 in https://windowsontheory.org/2013/05/06/reasons-to-care-in-honor-of-scott-aaronson/ https://windowsontheory.org/2013/05/06/reasons-to-care-in-ho...

pdonis 10y ago

> the theory shows that the decay have to be polynomial I thought this was the other way around: the theory predicts exact exponential decay, but experiments aren't entirely clear that that is always the case. Depending on which textbook or paper you read, some say the deviations from exact exponential decay are just experimental error, while others say they are evidence of additional effects that the exponential decay law does not account for.

stared 10y ago
It's clearly not that way you say. From quantum field theory, you get polynomial decay and it's quite fundamental (related to causality, holomorphic functions (Kramers–Kronig relations)) and if it were not working, a lot of physics would need rewriting. EDIT: I remember it from a lecture, many years ago. Some googling brings me to this thread with links to papers: http://physics.stackexchange.com/questions/7008/long-time-deviations-from-exponential-decay-in-radioactivity http://physics.stackexchange.com/questions/7008/long-time-de...
- pdonis 10y ago
  > From quantum field theory, you get polynomial decay I think you're oversimplifying, although I agree that I was also oversimplifying when I said that the theory predicts exact exponential decay. What I get from that stack exchange thread and the linked papers is this: in an idealized (and not physically possible for a real system) model in which every individual decay is statistically independent from every other and in which all of the quantum states that are possible end points of the decay are unoccupied, the theory predicts exact exponential decay. But in real physical systems, neither of those conditions is exactly true. Individual members of an ensemble of decaying quantum systems (such as radioactive atoms in a sample) interact with each other (either directly or indirectly via states in the environment), so their decays are not completely independent; and any real decaying system has an external environment which includes some occupied "target" quantum states. When these effects are taken into account, the theory predicts a decay law which is often called "power law" but which I would describe as more of a "truncated exponential": it replaces an infinite series of power law terms (the exact exponential) with a finite number of them. The actual measured decay law in a given experiment will depend on how much the experiment probes the portion of the state space where the above effects are significant (for example, a decay law measured over a very long time can deviate measurably from exponential where a measurement over a shorter time would not).

stared 10y ago

Wow, I got >=3 downvotes. Is the knowledge about non-exponential spontaneous emission so obvious?

eru 10y ago
Alas, please disregard early downvotes.

jgeada 10y ago

Well, there is the Landauer's principle (which is related to Maxwell's daemon): there is a physical lower limit to the cost of computations. https://en.wikipedia.org/wiki/Landauer%27s_principle https://en.wikipedia.org/wiki/Landauer%27s_principle So yes, there is a physical cost to non-reversible computation.

kanzure 10y ago
see also: "Ultimate physical limits to computation" http://arxiv.org/pdf/quant-ph/9908043v3.pdf http://arxiv.org/pdf/quant-ph/9908043v3.pdf "Limits on fundamental limits to computation" http://arxiv.org/pdf/1408.3821v2 http://arxiv.org/pdf/1408.3821v2 "The physics of information processing superobjects: daily life among the Jupiter brains" http://diyhpl.us/~bryan/papers2/The%20physics%20of%20information%20processing%20superobjects%20-%20Anders%20Sandberg%20-%201999.pdf http://diyhpl.us/~bryan/papers2/The%20physics%20of%20informa...

mmalone 10y ago

Personally, I consider it metaphysical because it says something about provability (since, deep down, proofs and programs are the same thing). Truth beyond proof (or at least beyond what's feasible to prove) is bizarre and mysterious. Metaphysics (and physics) is concerned with uncovering the fundamental truths of the universe. Computational complexity indicates this may be unachievable.

Natanael_L 10y ago

Looks like this is extremely relevant - the Halting problem and Turing completeness applied to quantum physics: http://phys.org/news/2015-12-quantum-physics-problem-unsolvable-godel.html http://phys.org/news/2015-12-quantum-physics-problem-unsolva... http://www.nature.com/nature/journal/v528/n7581/full/nature16059.html http://www.nature.com/nature/journal/v528/n7581/full/nature1...