EXERCISES
This
year I submitt all excercises in a single batch.
Answers
should be returned by the start of the second semester,
say
January 06 2003.
Submissions
should be returned preferably on paper. Electronic
submissions
may suffer from system incompatibilities
with
all consequences.
Cooperation between students is permitted under the following conditions:
--
the group shoudn't exceed three people.
--
the cooperation must be clearly indicated on all solutions submitted
--
a group starting to cooperate must persist in this cooperation till the
end
of the course.
--
the group will be graded as a collective; it is the responsibility of the
people cooperating to prevent abuses.
These excercises are in general
open ended: there exist no model solutions; rather the students are
invited to play with the structures
and algorithms, explore and invent constructions
resulting in the intended goals.
Just take time, have patience and enjoy yourself.
Please contact me if you are
uncertain whether some approach might work or not.
Game Theory.
A1.
i) Give a full analysis of the game from Donald Duck shown in class.
Game Description: There
is a pile of n matches on the table. In the example n
= 15.
Players in turn pick 1, 2 or
3 matches until no matches remain.
If the first player at this
time has an odd number of matches he wins; otherwise
his opponent wins.
Issues to be answered:
who wins the game for n = 15 ? Who wins the game for
general n; Show
that the behavior of the game is periodic.
ii) Next consider the following alternative game:
Player 1 may select 1,
2 or 3 matches
Player 2 may select 1
or 2 matches
Player 1 wins if
he terminates the game with X matches where X mod
5 equals 0 or 1
Player 2 wins if
she terminates the game with Y matches where Y mod
5 equals 2, 3 or 4
Issues to be investigated: depending
on the value of n this game becomes competitive, cooperative
or intermediate between the two. Investigate ! Provide a effective and
efficient desscription of the configurations in the game.
Bonus Extension: One can
further modify the game by changing either the set of numbers of matches
both players can pick up on
their turn (for example sequences with gaps like {1,2, 4} )
or the condition selecting the
winner when the game terminates.
Show that as long as the set
of numbers of matches a player can pick-up is fixed and finite
and the winning condition is
expressed by simple congruences the behavior of the game is
periodic in the number of matches
in the initial position of the game.
A2.
Napoleon Patience (at least under this name I learned
this solitaire game when I was a kid)
is played according to the following rules:
Take a deck of cards and place all 52 of them open
on a table in 4 rows of 13 cards. The actual
length of the rows however is 14 since there is an
empty place at the end of every row.
Legal moves are to place in an empty position behind
a card its successor in the same suit;
for example you may place the 4 of spades behind the
3 of spades but not behind the 3 of clubs.
An empty place in the first column may be filled by
an ace of any suit, but this ace should not
be removed from the first column.
(Thanks to the student who observed this error in the
original specification).
Purpose of the game is to rearrange by legal moves
the initial arrangement into a completely
well ordered deck: each row contains an entire suit
in its natural order. However, if an
empty position is created behind a king there is no
successor to place at this position,
and you are in trouble. Consequently, when all holes
follow one or more kings you
are stuck.
Evidently the rules of the game describe a huge graph (positions, connected by legal moves).
Frequently a pair of legal moves can be interchanged
- the order in which the moves
are executed doesn't matter. However it could also
be the case that performing a move
prohibits another move which you might have wanted
to perform. Show by means of an
example that selection of the right order is important:
give a position which you can win,
which becomes a lost position by performing the wrong
(legal) move.
In order to appreciate the importance of this observation:
Can a solitaire game remain interesting
if the possibility of a legal move is never preempted
by another legal move? What property of
the graph would hold in this case (Hint: think about
what you learned when studying Term
Rewriting Systems, in case you studied that subject).
Bonus exercise:
From the description it is not
evident that the game-graph is acyclic. Prove that it is (and
thereby prove termination of
the game).
PS: The way I learned the game you may twice
restart the game by rearranging the unsorted cards
behind the ones having obtained their final position,
thus creating 4 rows of 13 cards each
again; this increases the chance of winning the game.
For the purpose of this exercise however, this extension
is irrelevant.
The Tiling Game and its use in Reduction Theory
D1.
Design a variant of the reduction
of Turing Machine computations to the tiling game
where a legal tiling simulates
the computation of a two tape Turing Machine. It is no longer
required that the hight of the
resulting tiling is equal or proportional to the time of
the computation, but its width
should be proportional to the space used.
(Hint: invent a suitable
planar two dimensional representation of the time-space
diagram of a two tape TM)
D2.
In the reduction which shows
that BOUNDED TILING is NP-hard
it is implicitly assumed that
the description of the boundary condition is given by
explicit enumeration of the
sequence of colors along the boundary. One can
think of alternative descriptions,
where large sections of the boundary
are specified by mentioning
colors and stating how often these colors are repeated.
Show that under such a modification
BOUNDED TILING** becomes
NEXPTIME-hard.
The relation between PSPACE,
the Alternating Machine model and
logic description languages
and games.
E1.
Chlebus' reduction of Alternating Turing Machine computations
to
the 2-person tiling ame uses the restrictions on the
ATM model involved that
the states alternate between Universal and Existential
and that each instruction
moves the head of the ATM. Give a modified version
of this reduction which doesn't require
these restrictions on the ATM.
E2.
Consider two person games of the block moving type.
Players move in turn. There is an intitial stage where
both players place blocks on empty positions on the
board. Subsequently there is a stage where blocks which have
paced previously are moved around to other legal positions.
There is a collection of target configurations and the first
player to reach a target position wins the game. Blocks
are never to be removed from the board. Additional restrictions on legality
of moves may be introduced but should be minimized.
What is the upper bound on the complexity of endgame
analysis for this type of games which can be
obtained by aplication of the general theory on backward
induction?
Show how one can reduce the solitaire version of a
block moving game to this two person version.
(hint: tweak the rules of the two person version in
such a way that Urgat is forced to blindly copy
Thorgrim's moves at the penalty of immediate loss).
Which lower bound on the complexity of the
endgame analysis of these games follows from this
reduction?
Show how to reduce two person tiling to the above type of games.
Show how to reduce alternating
Polynomial Space bounded TM computations to this
type of games. Which lower bound
on the complexity of endgame analysis is obtained by such a reduction?
E3.
Consider the following version of QBF: XQBF
INSTANCE: A Logical formula of the form:
Qx1 Qx2 .... Qxk [ P(x1, x2, ... , xk) ]
where P is a propositional formula, the
xi are propositional variables and the
Q's are quantifiers of the form $!
or
"
; the quantifier $!
denotes "there exists
precisely one"
...
Question: is the formula true ?
Prove that this
problem XQBF still is PSPACE-complete.
The pebling game, used as a model
both for register allocation
and in the context of machine
model theory.
C1.
Prove that a complete binary
tree of depth k > 1 with 2k leafs
requires k+2
pebbles in the standard version of the pebble game
(no shifts allowed).
Is there a good reason to prefer
the Cook Pyramid over this binary tree
as a component in lowerbound
constructions in pebbling theory?
Interactive Proof systems and other models of interaction and/or randomized computation
F1.
Give an analysis showing that
in the interactive protocol for the
Permanent as described in the
Lund, Fortnow Karloff paper, the
lenghts of the messages which
must be exchanged are bounded by a polynomial
in the input length.
Note that this length involves
both the number of values which are transmitted
and their size as numbers (using
binary of decimal representations). The
lenghts can be estimated by
providing crude estimates for the values
which are transmitted.
F2.
#P is the class of functions
f(x) of the form f(x) := number of accepting
computations on input
x (for some P-time bounded fixed machine).
PP is the complexity class of
languages accepted by a probabilistic P-time
bounded machine by simple unqualified
majority (unbounded error model).
Papadimitriou observes that one
can show that #P functions can be computed in
polynomial time, using an oracle
for PP as additional tool (so membership questions
with respect to an PP language
can be answered in unit time). Describe a
construction which proves this
observation.