# Complexity Evaluation

#### View Solution

Erratum:

January 15th 7:30 PM: The example output for Problem 4 has been corrected.

• AC$$^0$$

• NP-hard

• PSPACE

• P

• P/poly

• Two distinct nodes $$a$$ and $$b$$ in the same bipartition of a bipartite graph are called friends if there are exactly two nodes in the other bipartition which are not adjacent to either $$a$$ or $$b$$. For a node $$v$$ in a bipartite graph, let $$f(v)$$ be $$1$$ if $$v$$ has no friends, and $$0$$ otherwise.

#### Input

• An undirected bipartite graph $$G$$, represented as an adjacency matrix, and

• A value $$k_v \in \{0,1\}$$ for each node $$v$$ in the top bipartition of $$G$$.

#### Output

True if every node $$v$$ in the top bipartition of $$G$$ satisfies $$k_v = f(v)$$, False otherwise.

#### Example Input for Problem 1

• $$G$$ is the following graph:

• $$k = (1,1,1)$$

#### Example Output for Problem 1

No pair of nodes in the top bipartition of $$G$$ is friends: nodes $$1$$ and $$3$$ have no nodes in the bottom bipartition which are not adjacent to either, and the other two pairs each have exactly one node in the bottom bipartition which is not adjacent to either. Hence, $$f(v)= 1$$ for all three nodes in the top bipartition, so we output True.

• In a bipartite graph $$G$$, a subset $$S$$ of the nodes of the top bipartition of $$G$$ and a subset $$T$$ of the nodes of the bottom bipartition are called a biclique if every node in $$S$$ is adjacent to every node in $$T$$. The size of the biclique is $$|S| \cdot |T|$$.

#### Input

• An undirected bipartite graph $$G$$, represented as an adjacency matrix, and

• An integer $$k$$, written in binary.

#### Output

True if $$k = 20 - C$$, where $$C$$ is the maximum size of a biclique in $$G$$, False otherwise.

#### Example Input for Problem 2

• $$G$$ is the following graph:

• $$k = 17$$

#### Example Output for Problem 2

$$G$$ has a biclique of size $$3$$ consisting of the third node of the top bipartition and its three neighbors, and no bigger biclique. Hence, $$C=3$$ so we output True.

• For positive integers $$n$$ and $$m$$, define the following quantities:

• $$f(n)$$ is the second-smallest distinct prime factor of $$n$$ if $$n$$ has at least two distinct prime factors. If a unique prime $$p$$ divides $$n$$, then $$f(n) = p$$, and if no prime divides $$n$$ (because $$n=1$$ or $$n=0$$) then $$f(n)=1$$.

• $$MOD(n,m)$$ is the integer $$q$$ with $$0 \leq q < m$$ such that $$n-q$$ is divisible by $$m$$.

A bipartite graph $$G$$ with $$n$$ nodes in the top bipartition and $$m$$ nodes in the bottom bipartition corresponds to a nonnegative integer $$c$$ defined by $$c=\sum_{i=0}^{m-1} d_i \cdot (n+1)^{i}$$, where $$d_i$$ is the degree of node $$i$$ in the bottom bipartition.

#### Input

• An undirected bipartite graph $$G$$, represented as an adjacency matrix,

• An integer $$k$$, written in binary, and

• A positive integer $$u$$, written in binary (with default value $$23$$ if none is provided).

#### Output

True if $$k = MOD(12 \cdot f(c) + 5,u)$$, where $$c$$ is the integer corresponding to $$G$$, False otherwise.

#### Example Input for Problem 3

• $$G$$ is the following graph:

• $$k = 18$$

#### Example Output for Problem 3

$$u=23$$ by default. We have $$n=3$$ and $$m=4$$, and so $$c = 2 \cdot 4^0 + 1 \cdot 4^1 + 1 \cdot 4^2 + 2 \cdot 4^3 = 150$$. Since $$150 = 2 \cdot 3 \cdot 5^2$$, it follows that $$f(c) = 3$$, so $$MOD(12 \cdot f(c) + 5,u) = MOD(41,23)=18$$, so we output True.

• For a bipartite graph $$G$$ let $$e(G)$$ denote the number of edges in $$G$$. For integers $$n,m$$ with $$m>0$$ define $$MOD(n,m)$$ to be the integer $$q$$ with $$0 \leq q < m$$ such that $$n-q$$ is divisible by $$m$$.

#### Input

• An undirected bipartite graph $$G$$, represented as an adjacency matrix, and

• An integer $$0\leq k < 341$$, written in binary.

#### Output

True if $$k = MOD(110 \cdot (e(G))^2 + 102 \cdot e(G),341)$$, False otherwise.

#### Example Input for Problem 4

• $$G$$ is the following graph:

• $$k = 139$$

#### Example Output for Problem 4

$$G$$ has $$6$$ edges, so $$MOD(110 \cdot 6^2 + 102 \cdot 6,341) = MOD(4572,341)=139$$, so we output True.

• A bipartite graph $$G$$ with $$n$$ nodes in the top bipartition and $$m$$ nodes in the bottom bipartition corresponds to a binary string $$s$$ of length $$m \cdot n$$ as follows: for any integers $$0 \leq i < n$$ and $$0 \leq j < m$$, bit $$(j + m\cdot i)$$ of $$s$$ is $$1$$ if there is an edge between node $$i$$ in the top bipartition and node $$j$$ in the bottom bipartition, and $$0$$ otherwise.

For a Turing machine $$T$$ and binary string $$s$$, we write $$t(T,s)$$ for the number of steps that $$T$$ takes before it halts when given $$s$$ as input, or $$-1$$ if $$T$$ never halts when given $$s$$ as input.

#### Input

• An undirected bipartite graph $$G$$, represented as an adjacency matrix,

• A positive integer $$k \geq 1$$, written in binary, and

• A Turing machine $$T$$, represented in binary (with default value the Turing machine from the example input if none is provided).

#### Output

True if $$k=t(T,s)$$, where $$s$$ is the binary string corresponding to $$G$$, False otherwise.

#### Example Input for Problem 5

• $$G$$ is the following graph:

• $$k = 6$$

• $$T$$ is the Turing Machine which starts at state $$0$$ and pointing at the left-most symbol on its tape, and has the following transition rules:

Current State Current Symbol New Symbol Direction New State
0 0 0 right 1
0 1 0 right 3
1 0 0 right 2
1 1 0 right 3
2 0 0 right halt
2 1 0 right 3
3 0 0 right 4
3 1 0 right 3
4 0 0 right 1
4 1 0 right 1

#### Example Output for Problem 5

$$G$$ corresponds to the binary string $$s = 110000011011$$. When the Turing Machine $$T$$ is run on $$s$$, the sequence of states it goes to at each step is $$0,3,3,4,1,2$$, and then $$T$$ halts. Hence, $$t(T,s) = 6$$, and so we output True.

• A bipartite graph $$G$$ with $$n$$ nodes in the top bipartition and $$m$$ nodes in the bottom bipartition corresponds to a binary string $$s$$ of length $$m \cdot n$$ as follows: for any integers $$0 \leq i < n$$ and $$0 \leq j < m$$, bit $$(i + n\cdot j)$$ of $$s$$ is $$1$$ if there is an edge between node $$i$$ in the top bipartition and node $$j$$ in the bottom bipartition, and $$0$$ otherwise.

For a Turing machine $$T$$ and binary string $$s$$, we write $$t(T,s)$$ for the number of steps that $$T$$ takes before it halts when given $$s$$ as input, or $$-1$$ if $$T$$ never halts when given $$s$$ as input.

#### Input

A triple $$(G,k,T)$$ represented in unary, consisting of

• An undirected bipartite graph $$G$$,

• A positive integer $$k \geq 1$$, and

• A Turing machine $$T$$ (with default value the Turing machine from the example input if none is provided).

#### Output

True if $$k=10+t(T,s)$$, where $$s$$ is the binary string corresponding to $$G$$, False otherwise.

#### Example Input for Problem 6

• $$G$$ is the following graph:

• $$k = 20$$

• $$T$$ is the Turing Machine which starts at state $$0$$ and pointing at the left-most symbol on its tape, and has the following transition rules:

Current State Current Symbol New Symbol Direction New State
0 0 0 right 0
0 1 0 right 1
1 0 0 right 2
1 1 0 right 1
2 0 0 right 3
2 1 0 right 4
3 0 0 right halt
3 1 0 right halt
4 0 0 right 5
4 1 0 right 4
5 0 0 right 5
5 1 0 right 3

#### Example Output for Problem 6

$$G$$ corresponds to the binary string $$s=101100001011$$. When the Turing Machine $$T$$ is run on $$s$$, the sequence of states it goes to at each step is $$0,1,2,4,4,5,5,5,5,3$$, and then $$T$$ halts. Hence, $$t(T,s) = 10$$, and so we output True.

• A matching in a bipartite graph $$G$$ is a set $$M$$ of edges of $$G$$ such that no two edges in $$M$$ are incident to the same vertex. A matching $$M$$ is a maximum matching if there are no other matchings with more edges than $$M$$.

Define the polynomial $$p(x) = 8x^2 - 78x + 178$$.

#### Input

• An undirected bipartite graph $$G$$, represented as an adjacency matrix, and

• An integer $$k$$, written in binary.

#### Output

True if $$k = b + p(a)$$, where $$a$$ is the number of edges in a maximum matching in $$G$$, and $$b$$ is the number of maximum matchings in $$G$$, False otherwise.

#### Example Input for Problem 7

• $$G$$ is the following graph:

• $$k = 19$$

#### Example Output for Problem 7

$$G$$ has three maximum matchings with $$3$$ edges in them. Hence, $$a=b=3$$, and $$p(a) = 16$$, so we output True.

✓ _ _ _ _ _ _ _

? _ _ _ _ _ _ _

X _ _ _ _ _ _ _