Simon's Algorithm | Hacker News Reader

Simon's Algorithm

leimao.github.io

41 pointskeyboardman13 comments

I don't understand the problem. x and y are free, so you can choose x=y. Then obviously, f(x)=f(y). Then it should follow x=x xor c, thus c=0. Or did they forget to claim that x and y are different?

Doesn't it read that "for all x, y \in {0, 1}^n"?

For 2^n of such pairs x, y, it happens that x = y. But checking the description of Simon's Problem on Wikipedia, it appears that case is excluded, so that x = y ⊕ c doesn't have to hold if x = y.

The problem is stated correctly. You are reading it incorrectly, but I am not sure how.

If c=0, then it says that f(x)=f(y) if and only if (<=>) x=y. In other words, for all x≠y, f(x)≠f(y). Thus the function is 1-to-1. This is a nontrivial property that is difficult to check.

The incorrect reading is that x and y are free. They're universally quantified, as you've said in your comment.

The first step you do when proving something all-quantified is making the quantified variables free.

Could you explain that a little for me? Do you mean substituting a term to show a counter-example?

If you want to prove "\forall x: A(x)", you start with "let x be a free variable. It remains to show A(x)".

Wouldn't that only show \exists x: A(x)? Or perhaps by free variable you mean one whose value isn't decidable - but that contradicts having chosen values in the origin comment.

The wikipedia article states it as f(x)=f(y) if and only if y is either x xor c _or_ equal to x. So it seems you're right.

https://en.wikipedia.org/wiki/Simon%27s_problem

You are confusing equality and equivalence.

It’s easy to do. Einstein did the same thing with E=mc2.

Equality is a matter of identity. Equivalence is a matter of behavior.

The speed of light is not an absolute constant as Einstein believed. C just represented the speed that light can travel as a relationship between energy and mass.

My favorite form of the equation is C equals the square root of energy divided by mass.

Behaviorally all that means is that as the energy to mass ratio goes up, the speed of light goes up. And as the mass to energy ratio goes up, the speed of light goes down. Hence time dilation, black holes, etc.

> The speed of light is not an absolute constant as Einstein believed. C just represented the speed that light can travel as a relationship between energy and mass. My favorite form of the equation is C equals the square root of energy divided by mass. Behaviorally all that means is that as the energy to mass ratio goes up, the speed of light goes up. And as the mass to energy ratio goes up, the speed of light goes down. Hence time dilation, black holes, etc.

That isn't what's happening in relativity. That might be a neat trick for you to remember whether an effect is dilation or contraction (though I personally find it more confusing), but the speed of light does not change in different frames of reference -- this is a fundamental property of relativity (and is an assertion by Einstein, who argued that the speed of light derived from Maxwell's equations means that if light functions in all frames of reference it must propagate at the same speed).

And while the mass-energy equivalence equation you mentioned is used in the way you described (rearranging it to have the speed of light as one term), it's actually used explicitly because the value must be constant -- the implication being that mass-energy is an invariant in relativity (though technically this derivation is backwards -- E=mc² is the conclusion you reach after assuming mass-energy conservation).

Relativity is already unintuitive enough, I personally find that adding incorrect-but-seemingly-intuitive explanations probably hurts your understanding more than it helps.

One of the (two) core assumptions that Einstein made with special relativity is absolutely that the speed of light in vacuum ("c"), is constant in every inertial reference frame/coordinate system. This has been borne out experimentally and the consequences of special relativity are seen every day at any particle accelerator (for e.g. time dilation of lifetimes of particles).

The full equation is:

E = mc^2 / sqrt(1 - v^2 / c^2)

This is coordinate/frame-dependent since it depends on speed. Here, m = mass of the particle which is also the same in every reference frame. You could define an effective mass as m' = m / sqrt(1 - v^2 / c^2) but that obscures the point imo.

To address your point directly, when you say "as the energy to mass ratio goes up, the speed of light goes up", that is just not true both mathematically and physically.

Reply on news.ycombinator.com