Tag: cosmology

P != NP

can NP-complete problems be solved efficiently in the physical universe? All hunches would say no, but then we only discovered polynomial time factorization using quantum algorithms 10 years ago.

2011-08-12: Markets being efficient and P != NP can’t both be true, it turns out. So either you can compute fast or make money on the stock market. It remains unclear whether you can MAKE MONEY FAST or not.
2017-01-04: The history of P != NP

In 1955, 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 2017, 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.

2022-12-03: Why are there complete problems, really?

This, then, is how universality of computation explains the existence of complete problems. For virtually any class we might define there will be a way of handicapping the universal computer such that it is still able to solve all of the problems in the class while at the same time not breaking the class specific resource constraint.

We can now see that the existence of complete problems is a direct result of one of the core features of computers that also makes them relevant to the real world.

String Theory

The final episode shows how in 1995 Edward Witten of Princeton’s Institute for Advanced Study, aided by others, revolutionized string theory by successfully uniting the 5 different versions into 1 theory that is cryptically named “M-theory,” a development that required a total of 11 dimensions. But the new 11th dimension is different from all the others, since it implies that strings can come in higher dimensional shapes called membranes, or “branes” for short. These possess truly science-fiction-like qualities, since in principle they can be as large as the universe. A brane can even be a universe — a parallel universe — and we may be living in one right now.

this is awesomely done. narrated by brian greene

Multiverse

you don’t need exotic theories to conjure multiverses. standard cosmology postulates that all possible quantum states (10^10^150), or world histories, actually play out. therefore, elvis is still alive (somewhere).
2007-01-28:

nice visualization of the multiverse.
2009-01-22: galaxy clusters racing at up to 1000 km / s – far faster than our best understanding of cosmology allows. Stranger still, every cluster seems to be rushing toward a small patch of sky between the constellations of Centaurus and Vela.
2012-01-23:

Recent theoretical works have shown that matter swapping between 2 parallel braneworlds could occur under the influence of magnetic vector potentials. In our visible world, galactic magnetism possibly produces a huge magnetic potential. As a consequence, this paper discusses the possibility to observe neutron disappearance into another braneworld in certain circumstances. The setup under consideration involves stored ultracold neutrons – in a vessel – which should exhibit a non-zero probability p to disappear into an invisible brane at each wall collision. An upper limit of p is assessed based on available experimental results. This value is then used to constrain the parameters of the theoretical model. Possible improvements of the experiments are discussed, including enhanced stimulated swapping by artificial means. The leap from our universe to another is theoretically possible. And the technology to test the idea is available today

that experiment sounds like nobel prize material.
2013-04-03: as good as any (perhaps even on the better side) episode of minutephysics

2015-05-28:

many physicists have come to doubt the very logic of nature’s laws. Increasingly, they worry that our universe might just be a random, rather bizarre permutation among uncountable other possible universes — an effective dead end in the quest for a coherent theory of nature

2015-08-11:

“A lot of people claim that you can never empirically test a claim like the multiverse because by definition you can only see what’s in our universe. But I think that’s much too quick.” Certain fundamental laws, which we can empirically prove in our own universe, might mathematically predict the existence of other universes. These laws would therefore be indirect, but compelling evidence of the existence of other universes.

Elegance

tuned into the elegant universe by chance. great, great show, not just for finally hearing the smartest man alive speak.

Although he is definitely a physicist (as his list of publications clearly shows) his command of mathematics is rivaled by few mathematicians, and his ability to interpret physical ideas in mathematical form is quite unique. Time and again he has surprised the mathematical community by his brilliant application of physical insight leading to new and deep mathematical theorems.

Free Will

Someone had an insightful comment about an age-old philosophical problem. namely the question whether free will exists. I am sure his argument has flaws, but is an interesting one to explore nevertheless.

I’m not sure that freewill, if it exists, requires any immeasurable quantum mechanical mumbo jumbo. The magic is not in any quantum mechanical phenomena inside the neurons, but in the standard physics arrangement of them.
More likely, the appearance of free will is result of the inability to perform 100% introspection into one’s own mind. I can no more “understand” the real-time machinations of my own mind than a Pentium processor can run a real-time simulation of its own transistors. Because I can’t perfectly introspect my subconscious, much of its output looks magically non-deterministic (hence the seeming similarity to quantum mechanical systems).
Any bounded-rational being would believe itself to have freewill based on its ability to take independent actions and its inability to introspect out all the causal factors underpinning its own actions. In reality, the system that creates intelligence can be 100% deterministic, just too complex for that intelligence to understand itself. Only a much more powerful intelligence could look down and see that these beings that think they have free will are actually operating on “simple” rules.

2007-03-23: Selecting for Gay Pagan Babies. Delicious logical quandaries.

Would the selection rob the child of free will? I don’t think so. What is being set is parts of personality traits, not the thoughts or reactions of the emerging person. They will bias and affect the thoughts, but no more and no less than any other personality traits. That these ones were selected does not give the parents more control over the child or predetermine its destiny. A theological argument against would be that God would make sure to give the right genome, and that parents should trust God to do it right. But if that is true, then God seems to like gays too.

2009-04-16: Strong Free Will Theorem. If indeed we humans have free will, then elementary particles already have their own small share of this valuable commodity.
2014-10-03: The free-will fix

New brain implants can restore autonomy to damaged minds, but can they settle the question of whether free will exists? If free will could be safely enhanced, would those with strengthened capacities be held to a higher standard?

2015-03-16: Is free will just an illusion?

We tend to take it for granted that conscious thoughts precede our actions. Indeed, our systems of morality, justice and moral responsibility are based on the notion that people are free to make thoughtful decisions. However, the US scientist Benjamin Libet’s groundbreaking 1980s experiments on the relationship between brain activity, conscious thoughts and physical actions caused some scientists and philosophers to rethink the concept of ‘free will’ and ask whether our decisions are made subconsciously before we’re even aware of them.

2019-03-13: QC & Free Will

Quantum computing theorist, popular author, blogger, and scientist Scott Aaronson on the #MeaningOfLife, Enlightenment, Schrodinger, Heisenberg, the Matrix, balancing work and family, and why the universe is not just a simulation.