Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[wierd]

It is basically the difference between linear and exponential functions, as it pertains to search or problem spaces.

Adding a few bits to the depth of a crypto schema exponentially increases the search scope you would need to comb to be assured you have found their key, if using a brute forcer, for instance.  That is an NP task. If you have the keys, and are given a cyphertext block, reconstructing the message is simple arithmetic; it is solved with an algebraic equation, in polynomial time, so P.

It need not be encryption that is the topic though, there are many things that are NP that hold up the wheels of progress. Take for instance, trying to simulate the folding of a protein.  A general proof that P=NP would open more doors than it closes.

[Max™]

Really it would open all the doors damn near.

Just scifi but still an idea of why P=NP would be a case of "oh yay we can do x now, oh shit, what about y and z though?" can be found in: http://www.antipope.org/charlie/blog-static/fiction/toast/toast.html

Polynomial time problems can be solved reasonably quickly by current computers, Non-Polynomial time problems can be verified by current computers if given a solution, but finding said solution could take orders of magnitude longer than the age of the universe in some cases.

Accordingly if I give you answer_a and used key_a to produce it, you can check and find what input_a was if you have key_a, but asking you to take answer_a and find which input_a and key_a were used to produce it? Good luck!

There are more complex permutations of that idea which form the basis for various public key encryption schemes, and whether you have secrets you want to keep or not, you need public key encryption to hold if you want to be able to trust that anything you receive from a page is what you requested from said page. Without it, would you be eager to order something online? Sign up for real world services online? Discuss meetings and such in real life with people online?

That there is no current way to convert P to NP is good news for how we use the internet, if we find one we're going to need to completely redesign everything from the ground up basically.

[Trekkin]

Well, how about that. P problems are simple and NP problems are impossible; I guess I should stop running my protein folding simulations, then?

P doesn't mean fast; it often just means predictably slow. Likewise, NP doesn't mean impossible. It just means we solve it stochastically for specific cases.

If P=NP, it is possible -- indeed, probable -- that the proof won't be constructive, because the polynomial solution to NP-hard problems could take longer than the stochastic solutions. Encryption wpuld be fine, one-way hashes safe, and proteins would still take a long time to fold; even just scoring them using cut-down pairwise function is O(n²) where n is the number of heavy atoms.

P versus NP is engaging fodder for techno-thrillers and a nice thing for armchair scientists to opine about on Wikipedia, but the odds that a proof either way changes anything for laypeople are low to nil.

[wierd]

Well, how about that. P problems are simple and NP problems are impossible; I guess I should stop running my protein folding simulations, then?

P doesn't mean fast; it often just means predictably slow. Likewise, NP doesn't mean impossible. It just means we solve it stochastically for specific cases.

If P=NP, it is possible -- indeed, probable -- that the proof won't be constructive, because the polynomial solution to NP-hard problems could take longer than the stochastic solutions. Encryption wpuld be fine, one-way hashes safe, and proteins would still take a long time to fold; even just scoring them using cut-down pairwise function is O(n²) where n is the number of heavy atoms.

P versus NP is engaging fodder for techno-thrillers and a nice thing for armchair scientists to opine about on Wikipedia, but the odds that a proof either way changes anything for laypeople are low to nil.

I did not say that the simulation of a protein was impossible; I said it was an NP task, and that its NP-ness is a holdup to very exciting science and medicine. Currently, the computational needs to perform the research requires the use of donated compute time on distributed compute clusters, such as Folding@hHome. If the researchers had to PAY for that compute time, the research would grind to a screeching halt.

A constructive P=NP proof, that reduces the computational burden for finding the valid solutions in the space, would allow the existing distributed compute farm to simulate many times its current output, on the same processing budget. The rate of research would increase dramatically.

The argument that sufficiently complex problems in the P class take inordinate amounts of time, does not mean that the NP version where P=!NP, is not an exponentially greater task to tackle, where the degree of burden grows exponentially with increase in N.  With P=NP in effect, that increase is only linear, not exponential. Linear CAN be computationally challenging, yes-- but exponential will always be more.

[Max™]

Yeah, the "could" in "could take the lifetime of the universe" not being a "definitely" is important there.

[Trekkin]

I did not say that the simulation of a protein was impossible; I said it was an NP task, and that its NP-ness is a holdup to very exciting science and medicine. Currently, the computational needs to perform the research requires the use of donated compute time on distributed compute clusters, such as Folding@hHome. If the researchers had to PAY for that compute time, the research would grind to a screeching halt.

Have you ever worked in research computing, weird? Or talked to someone who has? We pay for compute time by the CPU-hour all the time, and I haven't heard any screeching lately. Folding@Home isn't even the most cost-efficient way to fold proteins unless you use their multi-processor Markov processes to break up the problem, which requires making assumptions about the folding pathway that usually need ad hoc adjustment. It's just the one that's best advertised, since they need people to donate computing time.

Also, an exponential increase in computing complexity (time, if you like) for an increase in input is exactly what it means for a problem being in P. That's why their big-O notations have exponents in them. That exponent being 1 (and thus indicating a linear increase) is a subset of P.

I'm genuinely curious how you have come to think you know these things.

[Il Palazzo]

You know how the cosmological horizon is constantly approaching?

It isn't. It's receding.
See Fig.1 here:
https://arxiv.org/abs/astro-ph/0310808

I'm a bit confused by that, but it seems that the paper doesn't back you up.

Most observationally viable cosmological models have event horizons and in the ΛCDM model of Fig. 1, galaxies with redshift z ~1.8 are currently crossing our event horizon. These are the most distant objects from which we will ever be able to receive information about the present day.

I don't know whether this means that it's possible to go past the point where the cosmological event horizon will someday be, and thus cut yourself off whence you came. But things do disappear past the cosmological horizon.

...which isn't actually what you claimed. You claimed that the cosmological horizon is receding. I'm just confused now.

Cosmological horizon is receding, but galaxies are still leaving it (although they don't disappear*). These are two separate things.

The cosmological horizon is the distance from the observer from beyond which no signal can ever reach the observer, no matter how long a time passes.
On the graphs it is marked as 'event horizon'. As you can see (focus on the top graph - it has the 'everyday-meaning of distance' scale), the extent of the horizon grows with time (as you go up on the graph).
Today's horizon distance is approx. 16.5 Gly. This means that a galaxy today at the distance of 17 Gly is already beyond the horizon, and will not ever be able to send us any signals, or vice versa.
However, later on, when the horizon will have receded to 17.5 Gly, some other galaxy which will then find itself at 17 Gly will be able to send a signal that will eventually reach us.
Note that this will be a different galaxy. By the time the horizon recedes to 17.5 Gly, the galaxy today at 17 Gly will have been carried away by the expansion, and the galaxy that will then find itself at 17 Gly will be a galaxy which today is much closer.

On those same graphs you can see dotted lines marked with present-day redshifts (1, 10, 1000). This can be thought of as illustrating some test galaxies moving with the Hubble flow.
As you can see, these galaxies are constantly leaving the event horizon (their paths flare out with time). So, as time progresses, there are less and less galaxies whose signals sent TODAY can ever reach us.
And yet, this does not mean that the event horizon is approaching - it will always be moving measurably further and further away (asymptotically approaching 17.5 Gly).

This apparent incongruity, between galaxies leaving the horizon and the horizon receding, comes about as a result of the fact that when we're talking about signals being sent from galaxies, we're talking about light, which has nett velocity towards us, so it doesn't move with the Hubble flow like galaxies do.

*this is because the closer a galaxy is to the event horizon, the longer it takes for a signal sent from it to reach the observer. This time reaches infinity at the limit of the horizon (same as with black holes). As galaxies cross the event horizon, they leave behind images of themselves that will be in principle observable for the rest of the history of the universe.

[Dozebôm Lolumzalìs]

(Sorry for repeating your statements in my own words... repetitively... but that's how I check to make sure I understand.)

You know how the cosmological horizon is constantly approaching?

It isn't. It's receding.
See Fig.1 here:
https://arxiv.org/abs/astro-ph/0310808

I'm a bit confused by that, but it seems that the paper doesn't back you up.

Most observationally viable cosmological models have event horizons and in the ΛCDM model of Fig. 1, galaxies with redshift z ~1.8 are currently crossing our event horizon. These are the most distant objects from which we will ever be able to receive information about the present day.

I don't know whether this means that it's possible to go past the point where the cosmological event horizon will someday be, and thus cut yourself off whence you came. But things do disappear past the cosmological horizon.

...which isn't actually what you claimed. You claimed that the cosmological horizon is receding. I'm just confused now.

Cosmological horizon is receding, but galaxies are still leaving it (although they don't disappear*). These are two separate things.

The cosmological horizon is the distance from the observer from beyond which no signal can ever reach the observer, no matter how long a time passes.
On the graphs it is marked as 'event horizon'. As you can see (focus on the top graph - it has the 'everyday-meaning of distance' scale), the extent of the horizon grows with time (as you go up on the graph).

To make sure I understand the graph: the width of the event horizon line on the graph at any given height is the maximum distance a body can be from Earth, at that time, without being so far away that light emitted from the body at that time will never reach Earth, right?

Today's horizon distance is approx. 16.5 Gly. This means that a galaxy today at the distance of 17 Gly is already beyond the horizon, and will not ever be able to send us any signals, or vice versa.

Why is this different from the Hubble sphere? How do we know that it is 16.5?

However, later on, when the horizon will have receded to 17.5 Gly, some other galaxy which will then find itself at 17 Gly will be able to send a signal that will eventually reach us.

That galaxy which someday will be at 17 was previously nearer than 16.5, right?

Note that this will be a different galaxy. By the time the horizon recedes to 17.5 Gly, the galaxy today at 17 Gly will have been carried away by the expansion, and the galaxy that will then find itself at 17 Gly will be a galaxy which today is much closer.

Expansion of space, right? That's related to the increasing scale-factor on the right side of the chart?

On those same graphs you can see dotted lines marked with present-day redshifts (1, 10, 1000). This can be thought of as illustrating some test galaxies moving with the Hubble flow.
As you can see, these galaxies are constantly leaving the event horizon (their paths flare out with time). So, as time progresses, there are less and less galaxies whose signals sent TODAY can ever reach us.
And yet, this does not mean that the event horizon is approaching - it will always be moving measurably further and further away (asymptotically approaching 17.5 Gly).

Wait, the event horizon will be asymptotically approaching 17.5 Gly? That's the furthest it'll ever be? Why?

This apparent incongruity, between galaxies leaving the horizon and the horizon receding, comes about as a result of the fact that when we're talking about signals being sent from galaxies, we're talking about light, which has nett velocity towards us, so it doesn't move with the Hubble flow like galaxies do.

But why is the horizon even receding?

*this is because the closer a galaxy is to the event horizon, the longer it takes for a signal sent from it to reach the observer. This time reaches infinity at the limit of the horizon (same as with black holes). As galaxies cross the event horizon, they leave behind images of themselves that will be in principle observable for the rest of the history of the universe.

[Madman198237]

Does cosmological horizon refer to the expansion of the universe? Specifically, to the fact that the further away a galaxy is, the faster it is perceived to be moving? And that a galaxy beyond a certain distance from us would be moving, relative to us, faster than the speed of light (Away from us) and thus impossible to contact?

[TheDarkStar]

Does cosmological horizon refer to the expansion of the universe? Specifically, to the fact that the further away a galaxy is, the faster it is perceived to be moving? And that a galaxy beyond a certain distance from us would be moving, relative to us, faster than the speed of light (Away from us) and thus impossible to contact?

Yes. Things outside the nearby region of space are too far away to ever interact with because the space they're in is moving away from us faster than the speed of light and so they will never be able to interact with us.

[Madman198237]

Yes would have been quite sufficient, I think. Since you just kinda repeated what I said, and added a not-necessarily-true statement afterwards. If faster-than-light travel is possible, we could eventually reach any such galaxy that we desired. Of course, it would require IMMENSE amounts of energy, probably a task of a Type IV civilization, or even higher.

So, to clarify the entire discussion: The cosmological horizon is a sphere around us. Light from outside that sphere will never reach us, because of the ever-accelerating expansion of space. This expansion is increasing the distance that the emitted light must travel to reach us, and because space is expanding evenly, it moves the photons away from us faster than the speed of light (This is allowed because it is space that is expanding, and not a material that is moving).

At present, the furthest distance we can see is about 13.7 billion ly, in other words the distance light can travel over the entirety of the age of the universe. The light from anything past that distance has yet to reach us. Theoretically, however, the expansion of the universe means that there is a sphere, where the sum of the expansion of space is so large that light can't outrace it, and theory puts this sphere at about 17 Gly or whatever. Past this point, light emitted TODAY from that galaxy will never reach us. Light emitted BEFORE a galaxy crosses that line *will* be seen by us at some point, however as soon as it crosses that sphere it will not be heard from unless we do some serious travelling in that direction.

The Hubble sphere appears to be equivalent to said horizon, since both are affecting the same thing, if I'm not mistaken.

[TheDarkStar]

The edge of the observable universe is quite a bit further away from that (a google search tells me 45 billion light years), with "observable" meaning anything whose light will reach us in the future. Things very far away emitted their light when they were much closer.

On the other hand, the cosmological horizon appears to be the furthest distance at which mutual interaction is still possible.

[Madman198237]

Well, not really.

The observable universe is, right now, 13.7 billion ly in diameter. It will keep growing as the universe gets older and more light reaches us, but we will never see ANYTHING that happens beyond 17.5 Gly. In fact, you and I and everyone else on the forum are not likely to see anything that happens beyond 13.7 billion ly away, simply because humans don't live more than about a Planck time unit on the universe's clock.

[Il Palazzo]

To make sure I understand the graph: the width of the event horizon line on the graph at any given height is the maximum distance a body can be from Earth, at that time, without being so far away that light emitted from the body at that time will never reach Earth, right?

Yes.

Today's horizon distance is approx. 16.5 Gly. This means that a galaxy today at the distance of 17 Gly is already beyond the horizon, and will not ever be able to send us any signals, or vice versa.

Why is this different from the Hubble sphere? How do we know that it is 16.5?

The Hubble sphere is the present-day distance where the recession velocities reach 1 c. Numerically, is the inverse of the Hubble constant.
It would be equivalent to the event horizon, if we were living in a universe in which the Hubble constant does not decrease with time - i.e. in a universe with no matter or radiation, and solely with dark energy, or in a universe in which matter and radiation have diluted sufficiently to make it functionally equivalent.
Since we're living in a relatively young universe, in which H is still significantly decreasing due to the self attraction of its contents, it results in the Hubble sphere growing. This means that light emitted today at the Hubble radius will have 0 net velocity towards us, effectively hovering at a constant distance. But tomorrow, when H will have decreased ever so slightly, that light will find itself on our side of the Hubble sphere, and will be able to start approaching us.
That's why the Hubble sphere does not mark the event horizon - you can observe signals emitted from beyond it, as long as the emission wasn't too far away (within the actual event horizon).

The distance to the event horizon is determined by the composition of the energy density of the universe - for it to exist at all, the universe must have some dark energy content. Otherwise we could just wait sufficiently long and observe any signal we want, as recession velocities of any galaxy would never increase.

However, later on, when the horizon will have receded to 17.5 Gly, some other galaxy which will then find itself at 17 Gly will be able to send a signal that will eventually reach us.

That galaxy which someday will be at 17 was previously nearer than 16.5, right?

Yes. Otherwise it would have already been beyond the event horizon, and as such - by definition - would never be able to communicate its current state, no matter how long we waited.

Note that this will be a different galaxy. By the time the horizon recedes to 17.5 Gly, the galaxy today at 17 Gly will have been carried away by the expansion, and the galaxy that will then find itself at 17 Gly will be a galaxy which today is much closer.

Expansion of space, right? That's related to the increasing scale-factor on the right side of the chart?

Yes, these galaxies are carried away by the expansion of the universe.

On those same graphs you can see dotted lines marked with present-day redshifts (1, 10, 1000). This can be thought of as illustrating some test galaxies moving with the Hubble flow.
As you can see, these galaxies are constantly leaving the event horizon (their paths flare out with time). So, as time progresses, there are less and less galaxies whose signals sent TODAY can ever reach us.
And yet, this does not mean that the event horizon is approaching - it will always be moving measurably further and further away (asymptotically approaching 17.5 Gly).

Wait, the event horizon will be asymptotically approaching 17.5 Gly? That's the furthest it'll ever be? Why?

That's the distance at which in a universe with no matter or radiation, which has only dark energy in it, the recession velocities reach c. I.e., it's coincident with the Hubble sphere in such a universe. But in this universe, the rate of expansion (another name for the Hubble constant) does not decrease, and the resulting expansion is exponential.
A hypothetical light beam emitted at the Hubble sphere in this universe will always hover in place, never making any headway towards the observer, since for every light-second it travels, the dark energy expands the remaining distance by one light-second.

Our universe gets diluted with passing time - matter and radiation are progressively less able to retard expansion. On the other hand, dark energy remains constant (as fas as we can see) over time, so given enough waiting it will completely dominate the expansion, and the Hubble sphere in infinite future will coincide with the event horizon - whose distance is dependent on how much DE pushes the universe apart.

For it to grow beyond that, the dark energy would have to not be constant. If it were growing, that horizon would decrease without limit (leading to big rip). If it were decreasing, the horizon would always recede.

This apparent incongruity, between galaxies leaving the horizon and the horizon receding, comes about as a result of the fact that when we're talking about signals being sent from galaxies, we're talking about light, which has nett velocity towards us, so it doesn't move with the Hubble flow like galaxies do.

But why is the horizon even receding?

Because matter and energy are less and less capable of keeping dark energy from doing what it wants - i.e. expanding space exponentially, with some constant percentage rate per unit time.

At present, the furthest distance we can see is about 13.7 billion ly

There is no sense in which that distance is equivalent to light travel distance.
Here are the few distances that do make sense to talk about:
46 Gly is the present-day distance to where the regions that emitted CMBR are now (what is normally referred to as observable universe).
44 Mly was the distance to these same regions when they emitted CMBR.
~5 Gly is the farthest any of today-visible galaxies was at the time of emission of the light we receive.

Yes. Things outside the nearby region of space are too far away to ever interact with because the space they're in is moving away from us faster than the speed of light and so they will never be able to interact with us.

The Hubble sphere appears to be equivalent to said horizon, since both are affecting the same thing, if I'm not mistaken.

No, this isn't correct. Hubble sphere and event horizon are not equivalent. See the rest of this post. Or better yet, look at the graphs linked to earlier.

edit: I've got work to do. Be back later.

[Gentlefish]

Posting to re-SCIENCE up.