CSCE 411 Lecture 29

Lecture Slides

« previous | Monday, November 5, 2012 | next »

The Hat Game

Players cannot do better than 50%, but as a team, they can do much better by spreading out the "good guesses" and concentrating the "bad guesses"

In General

When played over all combinations with $n$ players, any strategy produces $k$ correct guesses and $k$ incorrect guesses. The best possible guess arrangement is:

1 correct guess per winning combination
$n$ correct guesses per losing combination

This is called a perfect strategy and cannot be obtained for certain numbers of players.

We've already solved for $n=3$ , but what about other $n$ ?

Finding a Perfect Strategy

Let $H$ be the set of all possible hat configurations (0 for one color, 1 for the other)

Let $\mathrm {dist} (H)$ be the number of places in which two elements of $H$ differ.

Example:

1 0 0 1 0 1 1 0 1
1 0 1 1 0 1 0 0 1

dist(H) = 2

Let a ball of radius $r$ around $h\in H$ be the set of all configurations whose distance from $h$ is at most $r$ .

Example:

h: 1001
B[1](H) = 0001, 1101, 1011,1000

Note that $|B_{1}(h)|=n+1$

Let $S$ be a deterministic strategy.

Let $L$ be the set of all hat configurations where a team playing according to $S$ loses.

Let $W$ be the set of all hat configurations where a team playing according to $S$ wins.

Note $L\cup W=H$ , and $L$ and $W$ are mutually exclusive and mutually exhaustive.

Suppose $h$ and $h'$ are elements of $H$ that differ only in the $i$ ^th entry.

According to $S$ , if Player $i$ guesses correctly in $h$ , then he guesses incorrectly in $h'$ , and vice versa.

Every element $h\in H$ is contained in a ball of radius 1 around some element of $L$ .

In a perfect strategy $S$ , the balls of radius 1 around l do not overlap

Let a Perfect code of length $n$ be a subset $L\in H$ such that the balls of radius 1 around the points of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} include all of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} and do not overlap.

A perfect strategy yields a perfect code:

Instructions for each player:

If the hat configuration might be in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} , guess so that if it's in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} , you'll be wrong.
If you can tell that the configuration is not in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} , pass.

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is a perfect strategy for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} players, then the probability of winning is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{n}{n+1}} .

Do perfect codes exist for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n > 3} ? Yes:

A perfect code of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} exists for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 2^m-1} .

Proof: A perfect code splits Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} into disjoint balls of radius 1. Each ball has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1} points and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} has 2^n points, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n} is divisible by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1} is a power of 2, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2^m-1}

NP-Completeness

Lecture Slides

Intrinsic hardness of problems.

NP = set of problems that can be checked quickly, but take a long time to solve (i.e. difficult)

Informal discussion: we will never get very formal in this course.

Polynomial Time Algorithms

Most of the algorithms we've seen so far run in time that is upper bounded by a polynomial in the input size (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^k)} ):

Sorting: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log{n})} .
Matrix Multiplication: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^3)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^{\log_2{7}})}
Graph Algorithms: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V+E)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(E \log{V})}

In fact, the running time of these algorithms are bounded by small polynomials.

Categorization

We call computational problem tractable iff it can be solved in polynomial time.

Decision Problems and Class P

Computational problem with yes/no answer is called a decision problem

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} is class of all tractable decision problems.