tsimionescu

> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.

This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.

Yes, I should have been more careful with the wording. Some problems have polynomial numbers of possible solutions, so for those there is no discussion of this kind. The more important point is that for some problems with a more-than-polynomial solution space (since even exponential is not precise enough, the solution space can be more than polynomial, such as n! for traveling salesman) we still have polynomial solutions, whereas for others we do not know of such algorithms.

The question can actually be generalized further - is it the case that for any solvable problem it's possible to find a solution without verifying every possible solution, and more specifically, only a tiny subset of the solution space? This would apply even beyond P vs NP, the same question would arise for EXP vs NEXP (that is, problems where we can find a solution vs just verify a given solution in exponential time), and same for factorial or Ackerman or any other complexity we want to imagine.

Looking at the problem in this way should also make it easier to construct a more strictly practical version of P vs NP, though it actually gets much harder to pin down details. That is, we can construct complexity classes that better match "what is plausibly solvable with a real computer" vs "what is plausibly verifiable with a real computer" and ask a similar question: given any problem of the second kind, can there be any generic algorithm of the first kind that would solve it?

Sounds so nice, for anyone who hasn't seen actual advertising in today's world, where only the absolute more clear and demonstrable lies are even theoretically illegal.

Unfortunately, the law only applies to objective claims that are false. It should apply to virtually all subjective claims as well.

Survivor is the opposite of how real human societies work - especially the tribal ones that thes show is aping. Real tribal societies are stable forever, and they are almost entirely related people (especially if we're talking about smaller tribes). You're reputation for helpfulness is crucial in any such society, so the kind of backroom dealing and betrayals the show is known for are almost entirely out of the question: if you are found out as a schemer, you don't get to go home to your real family, you risk being ostracized for the rest of your life.

But you can pick those other values as basis vectors, and they are just as good a choice as alive/dead. The only reason that you can say "the cat's brain doesn't experience those other states" is that you've presupposed a classical cat, that has some preferred basis. But this is just begging the question. We only get classical behavior when the wavefunction gets entangled with a classical object, but the math predicts you should also have non-classical "half-here" objects that would experience non-classical "half states" - and those are actually infinitely many.

So how did the classical world arise? Or how come we happen to be in the classical world, when there are infinitely many other non-classical observers? And note that the anthropic principle doesn't help here - all of the real laws of physics are the same for those other observers, you get the same chemistry etc, it's just the classical approximations that fail.

Specifically, decoherence provides a mathematical reason why we don't see self-interference and similar quantum phenomena on classical objects. It doesn't on its own explain why the single classical world arises from the infinitely many solution pairs to any quantum equation.

> There's no component of the wave function in which Schrodinger's cat experiences anything other than being alive or being dead.

The problem is that this is not what Schrodinger predicts, though. If |alive> and |dead> are valid solutions to the Schrodinger equation of some system, then so is any linear combination of them whose norm is one, such as 1/sqrt(2) |alive> + 1/sqrt(2) |dead>. So the math of QM predicts that there should be infinitely many cats that should feel partly alive and partly dead, many times more than the one live cat and the one dead cat. And yet you don't find this in any classical experiment.

Sure, but that has nothing to do with Kolmogorov complexity anymore, or with music enjoyment as a search for a patter - which was my original point.

Well, when we set an experiment up, we can measure in any basis we like, and get the corresponding results as probabilities per the Born rule, so I don't think there are any constraints on this. Plus, local interactions can't explain why the same classical basis arises globally - after all, when we investigate a distant star, it's never detected as being in some other basis then the local area.

Mostly a note, but the game was released 2 weeks ago. We'll see how well it sells, but it seems to be getting good reviews on Steam so far.

> Many worlds is just the Schrödinger equation without the wave function collapse.

It is not, it is the Schrödinger equation plus an extra rule that says that classical observers are only certain kinds of quantum states. There's no explanation in the MWI for why a device never reads out that a particle is 1/sqrt(2) |here> + 1/sqrt(2)|there>, even though that is exactly as probable a state as being |here>. And it turns out that this is exactly equivalent to positing wave function collapse / the Born rule.

And no, decoherence has nothing to do with this. Decoherence explains why there is no observable interference at the classical level between these states, not why you can only observe some states.

This is known as the preferred basis problem, for anyone who wants to read more about it.

While this might explain certain aspects of music, it doesn't explain the strong emotional reaction that music produces, even without lyrics. Kolmogorov complexity can't explain why Ode to Joy evokes so different feelings from Requiem, and why these feelings generally persist if you play the same notes with the same timings on very different instruments.

I imagine they might mean more like either early video game music (the kind produced by the same synthesizer the BIOS uses to emit beeps) and the style that mimics that, or extreme minimalism experiments in various musical disciplines.

There are some fundamental differences between liquids like water and gases like the air, they're not a continuum - moving from a liquid state to a gaseous state is a phase change, and comes with a huge, and measurable, energy cost (getting 1 kg of liquid water from 0C to 100C takes as much energy as converting that water entirely into water gas at 100C). Note that evaporation is different - it's just tiny bits of liquid water flying away.

Also, any atmosphere can carry any sound wave for at least some distance. It takes more or less energy to do so, and if the medium attenuates rapidly, you have to start with higher frequencies so that the right frequency reaches your audience, but that's it. You need different instruments to play in different atmospheres, sure, but not different music. And electrical instruments actually work exactly the same regardless of the medium.

Musical notes are pretty well defined sound frequencies. The medium which carries that sound wave is irrelevant. You can even get yourself a pair of bone conduction headphones, which would work for listening to music even if you were in a vacuum - since ultimately what matters is the sound wave hitting your ear bones, thr air is just the most common way for it to happen.

Of course, the sound that non-electrical instruments make is indeed dependent on the atmosphere in which they are played, assuming the same motions etc. You could probably make a violin produce the exact same sounds that it does on Earth playing it on Mars, but you'd have to play it differently than you do here. But even this doesn't apply to electrical instruments - Jimi Hendrix would sound the same if he could somehow play on the surface of Mars.

The English name of the country of ایران is Iran, pronounced "eye-ran", there's nothing wrong about that. Just like the English name of the country which calls itself Deutchsland is Germany. And the French name of the country that calls itself England is Angleterre, and the Japanese name for China is 中国 (chuugoku).

There is nothing wrong or weird about exonyms. Sometimes they happen to be relatively close to the endonym, sometimes they are not.

Oooops... I have no idea why I was certain they're from somewhere in Germany...

Neverwinter Nights 2 was made by Obsidian, not Bioware.

And I would argue Obsidian was the better studio anyway. Besides NWN2, and moreso its fantastic expansion, Mask of the Betrayer, they also made the excellent Knights of the Old Republic 2, Fallout: New Vegas, and their own original franchises, Pillars of Eternity 1 and 2, and Tyranny.

You're forgetting a few major ones:

- Baldur's Gate 3 (German)

- Disco Elysium (Estonian)

- Divinity: Original Sin 1 and 2 (same studio as BG3)

BG3 is notable for its gigantic success. And Disco Elysium is one of the best written games ever made, and it showed that you can have a fantastic RPG with no combat system whatsoever, while still having meaningful progression.

I don't think it's necessarily so. I view it more like garbage collection algorithms - the amount of garbage doesn't actually matter, you should only be looking at the roots of trust and down from there, and those will generally only lead you to more trustworthy content. The WSJ won't randomly link to fake TikTok accounts.

Now, the bigger problem happens if some of the trusted institutions and people go bad, for various reasons. If the NYT got bought out by Alex Jones, it might start mixing in lots of slop - but this is also a pre-existing problem.

The FDA has a very limited ability to regulate "truth". It has the single ability to regulate what standards something has to meet in order to be called "medication", and slightly more generally, in order to be advertisable with very specific health claims. But that's about it - you are absolutely free to sell snake oil as long as you don't call it medication and you don't, say, claim it specifically cures alopecia, but simply claim that it helps with hair growth. The gigantic health supplements and homeopathic and alternative remedies industry is testament to that.

I fail to see how any of this is even vaguely comparable to, say, stopping the spread of fake news. How would you write laws that allow the government to stop the spread of fake news, but not block the release of true but highly inconvenient news? For example, should Big Tech be allowed to spread news about the stolen US election, as the President of the United States calls it? How about the Genocide in Gaza, that the United Nations recognizes but that the United States calls fake news and antisemitic propaganda? And even if you have a clear opinion on which of these is fake news and which isn't, do you trust this administration and all future ones to have the same opinion?

And if I'm misunderstanding that you are talking about regulating the spread of fake news, please suggest what specific regulations you're thinking of.

You are generally right, except that you don't seem to know the history of major AWS outages. Failures in AWS in us-east-1, which is the first AWS cloud region, often cause cascading worldwide failures in the whole of AWS - especially failures related to DNS and to DynamoDB, if I remember correctly. That is, AWS workloada running in, say, eu-west-1 (and in fact in the whole of AWS) often start failing or at least having greatly degraded performance/availability because of a failure in AWS infra in their core region.

If AWS themselves can't handle cross region isolation and availability well, my expectations for most companies running on top of AWS are quite modest.

Regulating information, while it's fairly common at some levels (e.g. school manuals, one of the largest sources of legal information control, and one often abused for nationalistic lies in every country's history), is a very dangerous thing for governments to get into. Do you think the Trump government would be more likely to correct the NYT or Alex Jones if they had the ability to regulate news stories?

My whole point is that you have to trust people, that this is the only thing you can rely on for almost every important thing you care about. For food, for example, I don't eat from sketchy restaurants, unless I get some personal recommendations from friends about it. That is, I only eat from places where I think I have some reason to trust that the food is sanitary.

Also, I didn't say you need to access high quality sources for everything, I again kind of said the opposite: you choose who to trust for what, and that's that. There is nothing more, and has never been anything more, that you can do. Sometimes people and sources you trust will still lie to you, or be wrong, and you'll know wrong information - this is also unavoidable.

Of course, the more important some information is to you, the more effort you should actually spend trying to verify with multiple trusted sources. Some weird fact about cats you saw in a TikTok? Fine to just believe it. Trying to figure out who to vote for, or if the elections were stolen? Probably worth checking a few more sources. Read some definition for a word on Wikipedia, or some old historical event? Probably fine. Reading about an even slightly controversial topic? Check the actual sources, don't trust the snapshot you happen to see*.

Of course, the way LLMs work is antithetical to this, as information provided directly by the LLM is not coming from any human source you can decide if you should trust or not. So you shouldn't trust it for anything important, unless you can verify. But for information or disinformation on the web, nothing has changed, except maybe the quantities.

*for a silly example: the exact definition of the word "electrocution" is a slightly controversial topic - whether electrocution refers to any (significant) injury caused by electricity, or only death. Pedants soemwaht regularly edit the article on Wikipedia to remove the "or serious injury" part of the definition, despite it carrying a link to the OED that includes this mention.

Plenty of major programs are not signed, and thus plenty of organizations don't enforce code signing.

No, it doesn't. A certificate may or may not include CT info, or include fake CT info. Most TLS clients accept certificates without checking for CT.

How would you know it? If the CA was compromised, why would the attacker publish the fake certificates in CT?

Basically no one outside the major browsers verifies CT logs, so you can still attack a lot of people even without publishing.

It can't be in each other's gravity, else the same phenomenon would affect dark matter. For something to affect regular matter but not dark matter, it has to be an electromagnetic interaction (at this scale - as the weak and strong forces only interact on very very small distances). So it has to be a significant amount of head-on collisions, or some kind of charged dust clouds projecting large EM fields.

This is completely and utterly wrong. Google may put some effort into catching malware - but even that is limited to the more obvious cases. But for almost everything else, they put between 0 effort and negative effort into trustworthiness of the sources (e.g. they clearly favor big businesses for certain product searches regardless of quality).