Tag: algorithm

Possible Words

In general, if we have an alphabet of size A and look at length N words, the space of possible words is AN large and each word has just (A-1)N neighbors. Hence the fraction of neighbors declines nearly exponentially. The number of W(N) real words looks like a Poisson distribution with a peak around N=8 for English.

Exploring the space of possible words of length n, with visualization

Scott Aaronson

I have therefore reached a decision. From this day forward, my allegiances in the String Wars will be open for sale to the highest bidder. Like a cynical arms merchant, I will offer my computational-complexity and humor services to both sides, and publicly espouse the views of whichever side seems more interested in buying them at the moment. Fly me to an exotic enough location, put me up in a swank enough hotel, and the number of spacetime dimensions can be anything you want it to be: 4, 10, 11, or even 172.9+3πi.

i too, am a scott aaronson fan. his NP-completeness and physical reality is the snarkiest physics paper i have ever read. every now and then scott writes a paper that is a bit more widely accessible, like NP-complete Problems and Physical Reality. And now this one…
https://arxiv.org/abs/1108.1791
all i ever wanted to know about the intersection of quantum computing, cosmology, complexity theory etc

Intelligent Design Sort

The probability of the original input list being in the exact order it’s in is 1/(n!). There is such a small likelihood of this that it’s clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it’s safe to assume that it’s already optimally Sorted in some way that transcends our naïve mortal understanding of “ascending order”.

YouTube needs item authority

ie, deal with the multiple copies in a smart way. this reminds me of the tag consolidation manuel was talking about the other day, only much much harder.

When I worked at Amazon, there was a lot of effort into recognizing that 2 items in the catalog were actually the same item. That was called item authority. I was recently browsing around in YouTube and I noticed how bad the site is about dealing with multiple copies of the same content. For example, on Weird Al’s video, “White & Nerdy“, look at the related videos.

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.

Gates plays Petals Around the Rose

The game does work well with real dice. Comex reports that one major convention was largely disrupted when they arranged for the gift shop at the hotel to stock a large supply of dice, then introduced Petals Around the Rose to many conference attendees. “It was amazing, distinguished looking ladies and gentlemen in neat business clothes could be seen crawling on their hands and knees in little working groups all over the hotel. While speakers were saying important things on lecture platforms, the rattle of dice and mutterings about answers almost drowned them out from all over the dimly lit halls. We don’t like to do this too often. Makes enemies.”

Even the Microsoft guys agreed that Petals Around the Rose offers a good excuse for doing a bit of applications software. Indeed, Bill scratched out a program for the game on a napkin and passed it over the seat so that it could see daylight in Personal Computing.

heh. took me 2 min