A somewhat natural average-case NP-complete problem

A sampling NP problem is determined by an NP language L and distribution D that can be sampled in probabilistic polynomial time. The problem is to determine for an x sampled frome D whether x \in L. This is a model for the average-case complexity of an NP problem. It is a little known fact that there are “sampling-NP-complete” problems in a certain sense (definition here). Such problems are rarer and less likely to arise naturally than NP-complete, and so are less well known. An example of such a problem is: Given a Turing machine M, sampled by an exponential distribution on codes for Turing machines, and a uniformly random bitstring x, solve the 3SAT problem which is produced by running M on x for |x|^2 steps.

It strikes me that idealized forms of roguelike games such as Nethack could provide a somewhat natural example of a sampling NP complete problem, and this could give an intuitive picture of what such problems could look like. In such a game, the player explores a procedurally generated map trying to reach a particular target. The player must overcome a diverse variety of obstacles and can acquire a diverse variety of special items to help them. To make this fit the sampling NP framework assume this game is deterministic and perfect information and the player has a limited number of turns to reach the target (none of these are the case in most real roguelike games). Then in an arbitrary-sized world the player has a fixed probability of getting into this situation: The player is trapped in some region of the map with only a fixed particular set of items. The effects of these items interact in a peculiar way that imitate running a nondeterministic Turing machine with features of the map as input. If the playey can make the Turing machine accept then they can get to the next stage of the map, after which winning is routine.

Here’s a roughly outline of a more formal model that fits this schema:

Consider a finite 2D lattice of locked boxes (this generalizes easily to the infinite lattice). You have keys to boxes (0,0) and (1,0) and you want to open box (2,0). Within each box is either a white or black token, sampled uniformly. Each box also has two compartments containing a blue token and a red token, built such that opening one compartment destroys the contents of other. Finally, boxes (x,y) for x \geq 0 each have special keys that can open any box under suitable conditions: specifically, for each such key there’s a sequence (x_0, y_0, c_0), \dots, (x_{n-1}, y_{n-1}, c_{n-1}) where x_i, y_i \in \mathbb {Z} and c_i \in \{\mathrm {black}, \mathrm {white}, \mathrm {blue}, \mathrm {red}\}, such that the key opens box (x,y) when given the c_i-colored token from box (x+x_i, y+y_i) for each i. Tokens are reusable across multiple keys. At each box the key is sampled from some probability distribution supported on all the (countably-many) possible keys; for example, n could be sampled from an exponential distribution, each c_i sampled uniformly and x_i, y_i sampled from a discretized Gaussian distribution. Then the following happens with finite probability: The first two boxes have white tokens and the keys [(0, -1, \mathrm {white}), (1, -1, \mathrm {white})] and [(-1, -1, \mathrm {white}), (0, -1, \mathrm {white})]. This allows opening boxes (0,k) and (1,k) as long as both have white tokens. This occurs for n layers granting certain predetermined keys. Conditional on these keys being just right, the black token nucleates a pattern of open boxes with x<0 encoding the history of a 1D cellular automaton with both random and controllable inputs. This can emulate any NP problem with any sampling procedure. An ‘accept’ state can create a pattern of open boxes that spreads to the start site and to (2,0).


Prefix-free codes and ordinals

Consider the problem of representing a number in computer memory, which is idealized as a sequence of zeros and ones. The binary number system is a well-known solution to this problem — for example, the sequence “01101” represents 0 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 11. But there’s a problem: You don’t expect the entire computer to just be used to represent one number; you expect it to have other things stored afterwards. So how do you tell where the number ends? If the sequence begins 01101001\dots does this represent the number 011_2 or 01101_2 or 0110100_2?

The solution to this problem most commonly used in practice is to declare in advance a fixed number of bits that will be used to represent the number, usually 32 bits or 64 bits. For example, if we fix a 5-bit representation the 01101001\dots always means that the number is 01101_2 = 11 and 001\dots represents other stuff in memory. This works well enough in practice, but it has a problem: The number of bits you set aside for storing the number forces an upper limit on how big the number can be. For example, you cannot store any number bigger than 2^64 in 64 bits. If the computer ever needs to store a bigger number than can be represented with space set aside then the computer fails.

I’ll introduce some terminology. The condition that a system of representing numbers is unambiguous can be phrased formally by saying the this method is a prefix-free code. A prefix-free code consists of a set of codewords, which are sequences of bits, such that no codeword is a prefix of another. A continuing stream of bits can be interpreted as a codeword by taking an initial segment that is a codeword, and by prefix-free property at most one such interpretation is possible. Since we want this code to represent numbers we also want a map from the codewords to the natural numbers (by which I mean including zero, naturally)

Continue reading

Entropic Games

While trying to come up with mathematically interesting variants of the notion of a game, I’ve thought of this: What if each player was trying to maximize the entropy of their moves? You can imagine that each player has some message that she wants to transmit to some third party that can observe the move-history of the game but cannot receive any other information from the players. Then each player must balance the considerations of playing randomly to transmit more entropy at the moment versus playing moves that ensure that she’ll have a higher-entropy space of moves in the future.

For example, here are the rules for the entropic game Hot Potato: The game is played with one potato, that at each moment is possessed by one of the two platers. At a player’s turn, if she hold the potatoe she may either keep the potato or pass the potato on to the other player. If she does not have the potato she is forced to do nothing.

One strategy is for a player to give or keep the potato with even odds every time she has the potato. Then each move when she has the potato has an entropy of 1 bit, the maximum possible entropy for that move. However, this seems like a suboptimal strategy, since it doesn’t account for how keeping the potato is better than passing it: If you keep the potato you are guaranteed at a choice between keeping it and passing it next turn, but if you pass it you risk a zero-entropy move next turn if your opponent doesn’t pass it back. Thus you should keep the potato with better than even odds. However, even if keeping the potato is a better move you shouldn’t keep the potato all the time — that is a zero-entropy strategy.

And ordinary perfect-information two-player game can be made into an equivalent entropic game by giving the winning player a large entropic reward. That is, the winner is given an extra turn where she can recite a large amount of information — more than is needed to describe a game history not counting this move. Then the entropic incentive to reach a winning state is stronger than the entropic incentive to ranomize your moves before that, so players will mostly play as if they’re trying to win.

Here’s a formal model of entropic games: Suppose a player has n possible moves M_0, \dots, M_{n-1}. The player has analyzed that after playing M_i the expected entropy from all moves after that is S_i. Suppose she plays M_i with probability p_i. Then the total expected entropy is

S = \sum _{k=0} ^{n-1} p_k (\log p_k + S_i)

Optimizing this value, we get that

p_k = \frac {1} {Z} e^{-S_k}
Z = \sum_{k=0}^{n-1} e^{-S_k}

This is a Boltzmann distribution, like the probability distribution for a system in thermal equilibrium. Now, the anticipated entropies S_k can be calculated by taking expected values assuming the opponent picks her moves of the same form, and so on recursively.

Unlike ordinary combinatorial games this theory straightforwardly extends to more than two players. In ordinary game theory with three players there’s a indeterminacy with kingmaker positions, where a losing player must choose which of the two other players to make the winner. If a player faces two equally good positions in an entropic game, however, she will surely choose both with equal chances.

On Extraterrestial Life

I used to think that the interest astronomers seeking life on other planets have for exoplanets in the “Goldilocks zone” that can sustain liquid water, or for signs of water in this solar system, or for signs of complex organic molecules outside Earth, that this interest is misguided. After all, they’re looking for the materials that are the building blocks of life on this planet, but it’s perfectly possible that life on other planets is made out something completely different, such as having ammonia as a substrate or having silicon as the core constituent of complex molecules (and these are relatively mild modifications, they’re building life on the same general plan and just substituting one material for another). Perhaps searching for Earth-like life is the best scientists can do given the absence of any other information on what to expect aliens to be like, but we shouldn’t think these clues are actually the right guides for finding life on other planets.

However, thinking about this more carefully, I changed my mind. Let me explain:

Continue reading

Proof that DIGICOMP_EXP is in CC·#L

Three years ago, Scott Aaronson wrote the “paperlet” in blog title The Power of the Digi-Comp II: My First Conscious Paperlet. In it, he studies models of computation based on the mechanical computer Digi-Comp II, which employs balls rolling down switches and toggles. Using the so-called “pebbles model”, he shows that a natural generalization of Digi-Comp II to an arbitrary pattern of switches is equivalent in computational power to a complexity class called \mathsf {CC}. He also proposes a problem DIGICOMPEXP which represents simulating Digi-Comp II with a polynomially large network and an exponentially large number of pebbles, and poses the question of what is this problem’s computational complexity.

In the comments, I offer a proof that DIGICOMPEXP is hard for \mathsf{PL} (and the same proof can be extended to show that it’s hard for \mathsf {CC} \cdot \mathsf {PL}, by following the simulation of \mathsf {PL} in DIGICOMPEXP by an arbitrary \mathsf {CC} circuit). I then follow up with a proof that DIGICOMPEXP is in \mathsf {CC} \cdot \# \mathsf {L}. Although Aaronson was impressed by my first result, he was unable to follow and was unconvinced by my second result. I don’t blame him — at the time, I had difficulties with writing and specifically with explaining my mathematical thinking. Now that I have gotten better at writing and specifically I have much more experience with writing university-level problem sets in mathematics, I want to rewrite my second proof showing that DIGICOMPEXP is in \mathsf {CC} \cdot \# \mathsf {L}, hoping that it will be comprehensible this time.

On a side note, I want to remark that although \mathsf {CC} is a fairly obscure complexity class, Aaronson’s post was not my first exposure to the class, and my previous exposure was also in the context of a recreational mathematics problem: In the sandbox computer game Dwarf Fortress many players have built computers within the gameworld. It turns out that the amount of computation that is possible in a single timestep contains \mathsf {CC} through a mechanism that does not obviously extend to all of \mathsf {P}. For details, see my forum post here and my Stack Exchange question here.

Now, the proof:

In the following, I’m letting the variable names X, Y, Z denote nodes in the computational graph of the pebbles model. We denote that X splits into Y and Z by writing X \to (Y, Z), and that X and Y merge into Z by (X, Y) \to Z. Let C be the function that maps a node to how many pebbles pass through it in the DIGICOMPEXP computation. Then C is some suitable (exponentially large) constant in the starting node. Given a split X \to (Y, Z), we have C (Y) = \lceil X/2 \rceil and C (Z) = \lfloor X/2 \rfloor. Given a merge (X, Y) \to Z, we have C (Z) = C (X) + C (Y).

Now define another function W mapping nodes to dyadic rationals as follows: W maps the starting node to the same value as C. At a merge (X, Y) \to Z we have W (Z) = W (X) + W (Y) like with C. Finally, at a split X \to (Y, Z) we have W (Y) = W (Z) = W (X)/2. In words, W is like C except that a splitter always splits the pebbles evenly between the two piles, even if this leads to fractional pebbles.

Observe that W (X) can be expressed as a weighted count of the number of paths from the starting node to X, weighted by the 2 to the power of negative the number of splitters in each path. It follows that the binary digits of W are computable in \# \mathsf {L}. Next, I will show that C is \mathsf {CC}-computable in terms of W, and therefore DIGICOMPEXP is in \mathsf {CC} \cdot \# \mathsf {L}.

Define R (X) = C (X) - \lfloor W (X) \rfloor. Then R is 0 at the starting node. I will study how R behaves in the operations of splits and merges:

Consider a split X \to (Y, Z). Let c = \lfloor W (X) \rfloor \mod 2 be the binary units digit of W (X). Then

\lfloor W (X) \rfloor = 2 \left\lfloor \frac {\lfloor W (X) \rfloor} {2} \right\rfloor + c = 2 \lfloor W (X) / 2 \rfloor + c

It follows that

C (Y) = \left\lceil \frac {\lfloor W (X) \rfloor + R (X)} {2} \right\rceil = \left\lceil \lfloor W (X)/2 \rfloor + \frac {R (X) + c} {2} \right\rceil = \lfloor W (Y) \rfloor + \left\lceil \frac {R (X) + c} {2} \right\rceil

and so R (Y) = \lceil (R (X) + c)/2 \rceil. By a similar argument we have R (Z) = \lfloor (R (X) + c)/2 \rfloor.

Next, consider a merge (X, Y) \to Z. Observe that \lfloor W (Z) \rfloor = \lfloor W (X) + W (Y) \rfloor = \lfloor W (X) \rfloor + \lfloor W (Y) \rfloor + \lfloor \{W (X)\} + \{W (Y)\} \rfloor. Since C (Z) = C (X) + C (Y), it follows that R (Z) = R (X) + R (Y) - \lfloor \{W (X)\} + \{W (Y)\} \rfloor. Note that \lfloor \{W (X)\} + \{W (Y)\} \rfloor is the unit digit of the sum of the fractional parts of W (X) and W (Y), and so is \mathsf {CC}-computable in terms of W because binary addition is \mathsf {CC}-computable.

In conclusion, it is possible to compute the R value of an arbitrary node using the operations R \mapsto (\lceil R/2 \rceil, \lfloor R/2 \rfloor), (R_0, R_1) \mapsto R_0+R_1 and R \mapsto R+c where c is a small integer that’s \mathsf{CC}-computable given the values of W, and this computation does not need any fanout. Moreover, R (X) has a polynomial bound. This is like the pebbles model, except that the number of pebbles may be negative. This integral pebbles model may be emulated by the ordinary pebbles model by representing a possibly negative amount x in an integral pebble pile by x+N in an ordinary pebble pile where N is an even number large enough to guarantee that x+N is nonnegative. Then the splitting and merging operations on x are represented by the same operations on x+N, followed by adding or subtracting an appropriate constant. Finally, the output of the DIGICOMPEXP computation is given by whether C (Z) = \lfloor W (Z) \rfloor + R (Z) is positive for some terminal node Z, which is \mathsf {CC}-computable in terms of the binary digits of W (Z) and R (Z) + N in unary.

The Official Rules for Modal Combat

1 A game of Modal Combat begins when there is common knowledge among each of the players that they would like to play Modal Combat.

1.1 The above rule does not apply when a subset of the players have already begun a game of modal combat. However, any person can an ongoing game by reaching common knowledge with the current players that they would like to join.

1.2 In the Nomic variant of Modal Combat, additional rules are created when there is common knowledge among the players that such rules are necessary.

2 It is common knowledge among the players that all players obey the rules of Modal Combat

2.1 In particular, the rules of Modal Combat are common knowledge.

2.1.1 If at any point the rules of Modal Combat contain ambiguities or offer difficulties in their interpretation or application, then the proper way to resolve these difficulties or ambiguities is common knowledge.

3 All players are required to reason in a prefectly rational manner at all times.

3.1 All players must act in accordance with their personal self-interest to the maximal extent allowed by the rules of the game.

4 To avoid any unsportsman-like play, all players are required to disclose any remedy, immunity (innate or acquired), or antidote to any poison, elixir, or powder before the first turn of the game.

5 Any player may view the source code for any other player.

5.1 However, each player can change his or her source code at any time.

6 Each player must either:

(i) Always tell the truth.

(ii) Always lies.

(iii) Always randomly decide between telling the truth or lying based on a perfectly fair and unpredictable coin toss.

7 In a prisoner’s dilemma, a player must cooperate if and only if the player can prove that his or her opponent can prove that the player can prove that if the player’s opponent cooperates then the player will cooperate if and only the opponent is following this rule.

8 One of the player is designated the barber. The barber must shave every player and only those players that don’t shave themselves.

9 Once a player knows what his or her own eye color is, that player instantly loses.

10 Whereof one cannot speak, one must remain silent.

Why I Am Changing My Mind About AI Risk

The following is pretty unpolished, and except for some minor edits was written a long time before I published it. It might not be representative of my current thoughts in multiple ways. Nonetheless I think publishing it will be more honest and informative than not publishing it.

I have long been an observer of Less Wrong and the rationality movement. When I first read Eliezer Yudkowsky’s Sequences (around 2010) I was very entertained by them for being well-written texts which, as I thought, got a surprising amount of difficult questions right. Of course, there were many points where I disagreed with him, and still do. When I read his futurist articles, they made sense, but I was skeptical. Their point of view was weird, but there was a sense I found that appealing — I had already thought it likely that a truely rational look at our world be equally weird, so I saw it fitting in some sense with the rest of the Sequences’ rationalist messages. Arguments, that were more popular during the early history of Less Wrong, that even with a small chance of success donating to SIAI (as MIRI was then called) had an enourmous expected value did not convince me, but would occasionally frighten me when I thought about it.

I decided to hold off before making decisions, think about things some more, and definitely don’t give them money while there’s a large chance they’re looneys. So I gave myself time to think about the arguments for or against. Eventually (I believe around 2012 or 2011) I decided that AI risk and its proponents really is ridiculous.

I am now in the process of changing my mind about this. Here are three reasons why:

  1. I am amazed by the past progress of AI in the past few years using convolutional and recurrent neural networks. In particular, the observation that underlying the large variety of recent achievements is a relatively small set of relatively simple ideas suggests to me that there really is an underlying method behind “general-purpose” and that we have found a piece of it. Whereas beforehand I was unconvinced that any line of research could be known to have relevance on future general AI, I see this as a possible counterexample.

  2. My opinion on the issue is influenced by my impression of what other people think about it. I try to be open and unrepentant about this — I believe that learning from the collective opinions of thers is rational. AI risk did not look good. It was mostly only discussed seriously in a single community over a small number of websites. While the advocates claimed they are doing a technical research program, they were to a large extent unconnected to academia, and were fundraising to the public rather than institutions qualified to judge them on a technical basis, which is suspicious.

    This is changing. Although AI risk is still not mainstream, it has gotten much bigger than it used to be. I now believe that even if I hadn’t initially gotten into Less Wrong when I did I still would have been exposed to these ideas. And now that there are more players in the game I can better mentally seperate the questions of whether MIRI is any good and whether AI risk as a whole is important.

    In retrospect it seems like I did not react to this factor as quickly as I could have.

  3. Over the past two years, I have undergone a period of psychological hardship, and I worry it had affected my cognition. In particular, it would have increased my positive affect to the rationalist community. Optimistically, this let me look at the issues in a new light unbiased by my prior preconceptions. Pessimistically, in a moment of weakness I have let new opinions enter without examining them with due diligence, and a subtle flaw lies hidden. I imagine another person in my situation might become religious.

Of these reasons, the most worrying is the first one — it says we might not have much time. The third one is also worrying to me on a personal level.

In the short term, here are some things that I think of doing:

  1. I still disagree in significant ways with many of the positions current advocates have on the details of AI risk. I hope I’ll be able to write up my thoughts on this matter, and that people will give it enough attention either to be convinced or to take the time to convince me otherwise. Currently the writer I’ve seen whose opinion most resembles mine is Paul Christiano.

  2. Seeing as I’m still not sure, and may never will be, about AI risk, I intend to be on the lookout for any reason to change my mind again. Unfortunately if I start thinking of myself as seriously committed to AI risk changing my mind will be more difficult.

Edit (2017-01-04): Changed title from “Why I Changed My Mind About AI Risk”. This is the title I was intending and don’t know why I ended up writing “changed” instead of “am changing”.