Everything You Need to Know About NP-Completeness: 1

Part II →

Let's play a game.

THE RULES

Number of players: 2
Materials needed: 2 pencils, scratch paper.

ORDER OF PLAY:

■To begin the game, one of the two players names a mathematical (counting) problem, and how many tries it will take her to solve it.  She may generalize the number of tries as an equation.  The problem may be as general or specific as she like.

She should write this information down on a piece of paper, and give it to the second player.
She is now Player 1.
This ends her turn.

■Player 2 now has at least two choices.**
     1) She can change one and only one element of the problem by making the necessary alterations to the text.  She returns the paper to Player 1.

     2) She can challenge Player 1 to solve an instance of the problem in the stated time.
She may not do both.  This ends her turn.

■Player 1
    1)  If the problem has been changed,  she must  offer a new number, or equation, to describe the amount of time it will take her to solve the revised version of the problem.
She may also Dispute the Change, as described below.
She then returns the paper to Player 2.
This ends her turn.

Play returns to Player 2, who has the same choices as her previous turn.

     2) If Player 1 has been challenged, she must then solve the instance of the problem.  If the solution is an equation, it must be of the same order as what she has written on the previous turn.
If she is successful, she WINS, and if not she LOSES.

■Ending the Game

Play repeats until  Player 2 challenges Player 1, at which point one of the players will WIN and the other will LOSE.

**I have selected two choices, to demonstrate a winning strategy.   Players 1 and 2 are free to invent any number of alternatives.  Player 2 may, for example, decide to play airplane instead.  Though it is unlikely to help Player 2 win the game, I will not argue with the merits of this choice.  If you do not know what I mean, then when you reach the end of this sentence, I ask you to stop reading, step away from the computer, and play airplane.

There is no wrong way to play.

SPECIAL RULES

• Disupting a change:  When  Player two changes the problem, there must be agreement that only one element has been changed.  There need not be a precise definition of "element", but a successful dispute must be mathematically sound: she must name an alternative change which satisfies the following sentence.
   "The change made by Player 2 is composed of this change, and at least one other."She is not required to identify the other change(s).  She does not have to offer a time in which she can solve her change.  If her dispute satisfies the sentence, and the composition is mathematical, then the dispute carries.  
     a) The disupte is successful, the problem is returned to Player 2, who may agree to the change made by Player 1, or offer a new one, following the same rules as before.  In either case, this ends her turn.
  
  It is now Player 1's turn. 
        If Player 2 agrees: Player 1 cannot dispute her own change. She must now solve the problem
        If Player 2 offers a new change: Play passes to Player 1 in the usual way and she has the right to dispute the change. 
     b) The dispute is unsuccessful:  Player 1 resumes her turn and must offer a solution time in the usual way.
    c) If no agreement can be reached, the game is DRAWN.  A draw is not a permanent state.  If one player demonstrate a resolution which is accepted by both players, play resumes.   

• Time limits:  There are no time limits on any action.

The rules are incomplete. The game can be improved by playing it. If a rule fails to help us identify the structure of a problem, we should change it.

But the rules are just for fun; an invitation.

A WAGER

I will be player 1.  Would you like to be Player 2?  Have a seat.  See?  I even have cookies and tea.

I say that you, Player 2, can always win.

What is the winning procedure?  {My answer}

■

__________________________________

In the attic of the theater: Anna, in perriwinkle tights. 

Tucked in the prow of a small boat, his room meanders on and off stage.  Boys and girls in white shirts and blue caps, blue ribbons around the waist, march down the tiny stairwells; left, right, zigzag.  Pointed newspaper hats and painted wood swords.  Anna, perched in the rafters.  Two seamstresses, green eyes, and dense, blanket legs, sew shut her shoulders.  The cloth falls aside and she is again mottled pink-and-white.  And the blue, crawling up her sides.  Two cloth frowns, the seamstresses drift away.

 When time is akilter, his room hovers translucent over the crowd, he threads the muscles of his arms and legs through the pulleys, stretches his back along the walls, crouches behind the sets, each with a small network of baskets and chairs and roomless corners for him. He watches the attic, invisible.

The bows.

The cast walks on and off, and she among them.  In a clatter and clump, toy trumpets, they proceed through the left wall of his kitchen and vanish.  Anna stops.  When she puts her hands on him, the muscles unhook from the pulleys.  Concave limbs bound in circles unbind, fatten.  Into his right hand she places the slow winding and unwinding of her skin --in and out of blue--,  and breathes it into his mouth.  The two pour from finger to tongue, in the attic of the theater.  Her fingers bloom. His wrists fall open in orange circles of sleep, and in the evening their skin falls as sunlight on the faces below.  Leaf-tongued, his words spiral her thighs, and her mouth flowers around his neck, murmurs in the deepening furrow of his spine.