%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the “author” and “collaborators” fields as
% appropriate. Write your solutions where indicated.
%
\def\inclsolns{0}
\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{hyperref}
\usepackage{amsmath,amssymb,amsthm}
\input{macros}
\theoremstyle{definition}
\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi
\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother
\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}
\begin{document}
\begin{center}
{\Large CS 535: Complexity Theory, Fall 2020}
\bigskip
{\Large Homework 1}
\smallskip
Due: 8:00PM, Friday, September 11, 2020.
\end{center}
\ifnum\inclsolns=1
\makeatletter
\noindent Name: \@author \\
Collaborators: \@collaborators
\makeatother
\else
\fi
\paragraph{Reminder.}
Homework must be typeset with \LaTeX\ preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions {\em by
yourself without assistance}. You must also identify your
collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the
Web or students not enrolled in the class is strictly forbidden.
\begin{problem}[Collaboration Policy] Read and sign the course Collaboration and Honesty Policy ({\footnotesize \href{https://cs-people.bu.edu/mbun/courses/535\_F20/handouts/collaboration.pdf}{https://cs-people.bu.edu/mbun/courses/535\_F20/handouts/collaboration.pdf}}) and upload it to Gradescope. An electronic signature is fine.
\end{problem}
\begin{solution}
Your solution here.
\end{solution}
\begin{problem}[Random Pizza Party]
Uncle Mark’s Pizza shop bakes pizzas with a huge number of possible toppings. You are hosting a pizza party for $n$ very persnickety guests, numbered $1, \dots, n$. Every guest \emph{likes} some set consisting of $k$ toppings, and \emph{dislikes} a disjoint set consisting of $k$ toppings. A guest will only eat a pizza if it has all of the toppings they like and has none of the toppings they dislike. However, the guests don’t eat much, so arbitrarily many guests can share any given pizza. Being a good host, you want to order a wide enough variety of pizzas so that every guest will have something to eat.
\begin{enumerate}[(a)]
\item Consider a random pizza that includes each possible topping independently with probability $1/2$. What is the probability that any particular guest $i$ is willing to eat this pizza?
\begin{solution}
Your solution here.
\end{solution}
\item Suppose you order $m$ random pizzas independently according to the above process. What is the probability that guest $i$ is willing to eat \emph{none} of the pizzas you ordered? Your answer should only depend on $k$ and $m$.
\begin{solution}
Your solution here.
\end{solution}
\item Show that regardless of your guests’ preferences, there exists a way to order $m = 2^{O(k)} \log n$ pizzas such that every guest will have something to eat.
\smallskip
Hint 1: Use the \emph{probabilistic method}. Show that if you order $m = 2^{O(k)} \log n$ random pizzas, then the probability that there exists a guest who can eat none of the pizzas is strictly smaller than $1$.
\smallskip
Hint 2: You may find the following inequality helpful: $(1 – 1/x)^x \le \frac{1}{e}$ for all $x > 1$.
\begin{solution}
Your solution here.
\end{solution}
\end{enumerate}
\end{problem}
\begin{problem}[Encodings]
An encoding is an unambiguous way to represent an object, e.g., a natural number, a graph, or a Turing machine, as a string in $\Sigma^*$ for some alphabet $\Sigma$. Encodings allow us to present complex objects as inputs to Turing machines and other computational devices. Following Section 1.4 of Arora-Barak, one way to formalize a \emph{nice encoding} of a set of objects $D$ is as a function $f: \Sigma^* \to D$ such that, for every $y \in D$, there are infinitely many $x \in \Sigma^*$ such that $f(x) = y$. (Check that this indeed formalizes the discussion there!)
\smallskip
We will typically fix a reasonable, unspecified way of encoding objects as binary strings (strings over the binary alphabet $\Sigma = \{0, 1\}$) and refer to an object and its shortest encoding interchangeably. But it’s sometimes worth keeping in mind how the choice of encoding affects the statements we can prove.
\begin{enumerate}[(a)]
\item Show that the set of Turing machines $\mathcal{M}$ can be nicely encoded in a unary alphabet $\Sigma = \{1\}$ via a function $f_1 : \{1\}^* \to \mathcal{M}$. You may use without proof the fact that Turing machines can be nicely encoded in binary as described in Section 1.4.
\begin{solution}
Your solution here.
\end{solution}
\item A unary language $L$ is a language over the alphabet $\{1\}$, i.e., $L \subseteq \{1\}^*$. Show that there is an undecidable unary language.
\begin{solution}
Your solution here.
\end{solution}
\end{enumerate}
\end{problem}
\end{document}