STEMS 2021 CS Cat B

Part of 2021 India STEMS

Subcontests

(5)

1

Complexity Problem

Let's say a language

L \subseteq \{0,1\}^*

<span class='latex-bold'>P</span>_{angel}

if there exists a polynomial

p : \mathbb{N} \mapsto \mathbb{N}

, a sequence of strings

\{\alpha_n\}_{n \in \mathbb{N}}

\alpha_n \in \{0,1\}^{p(n)}

, and a deterministic polynomial time Turing Machine

M

such that for every

x \in \{0,1\}^n

x \in L \Leftrightarrow M(x, \alpha_n) = 1

\alpha_n

to be the angel string for all

x

n

. Note that the angel string is

<span class='latex-bold'>not</span>

similar to a witness or certificate as used in the definition of

<span class='latex-bold'>NP</span>

For example, all unary languages, even

UHALT

which is undecidable, are in

<span class='latex-bold'>P</span>_{angel}

because the angel string can simply be a single bit that tells us if the given unary string is in

UHALT

or not. \\\\
A set

S \subseteq \Sigma^*

is said to be sparse if there exists a polynomial

p : \mathbb{N} \mapsto \mathbb{N}

such that for each

n \in \mathbb{N}

, the number of strings of length

n

S

p(n)

. In other words,

|S^{=n}| \leq p(n)

S^{=n} \subseteq S

contains all the strings in

S

that are of length

n

k \in \mathbb{N}

S_1, S_2 \ldots S_k

, show that there exists a sparse set

S

and a deterministic polynomial time TM

M

with oracle access to

S

such that given an input

\langle x,i \rangle

M

will accept it if and only if

x \in S_i

. \\Define the set

S

(note that it need not be computable), and give the description of

M

S

. \\Note that a TM

M

with oracle access to

S

can query whether

s \in S

and get the correct answer in return in constant time. [/*] [*] Let us define a variant of

<span class='latex-bold'>P</span>_{angel}

<span class='latex-bold'>P</span>_{bad-angel}

with a constraint that there should exists a polynomial time algorithm that can compute the angel string for any length

n \in \mathbb{N}

. In other words, there is a poly-time algorithm

A

\alpha_n = A(n)

<span class='latex-bold'>P</span> =<span class='latex-bold'>P</span>_{bad-angel}

<span class='latex-bold'>NP</span>=<span class='latex-bold'>P</span>_{bad-angel}

? Justify. [/*] [*] Let the language

L \in

<span class='latex-bold'>P</span>_{angel}

. Show that there exists a sparse set

S_L

and a deterministic polynomial time TM

M

with oracle access to

S_L

that can decide the language

L

1

Prove that set is spectrum

M

of natural numbers is called a spectrum if there is a first-order language

L

\phi

L

M = \{ n \mid \phi \text{ has a model containing exactly $n$ elements}\}

For example, consider a sentence

\phi = \exists e . (\forall x. x = e)

in a first order language with no relation symbol, no function symbol, and no constant symbol. The formula

\phi

only admits a model containing exactly 1 element. Therefore, the set

\{1\}

is a spectrum.\\ Show that:
[*] Every finite subset of

\mathbb{N} \setminus \{0\}

is a spectrum [/*] [*] The set of even numbers, i.e.,

\{2k \mid k \in \mathbb{N}\}

is a spectrum [/*] [*] For any fixed

m \geq 1

, the set of numbers greater than

0

that are divisible by

m

\{m\cdot k \mid k \in \mathbb{N}\}

is a spectrum[/*]

1

Good is regular

\Sigma

be a finite set. For

x,y \in \Sigma^{\ast}

x\preceq y

x

is a sub-string (not necessarily contiguous) of

y

ac \preceq abc

. We call a set

S\subseteq \Sigma^{\ast}

\forall x,y \in \Sigma^{\ast}

x\preceq y, \; y \in S \; \; \; \Rightarrow \; x\in S .

Prove or disprove: Every good set is regular.

1

Remains a forest

Given two forests

A

B

V(A) = V(B)

, that is the graphs are over same vertex set. Suppose

A

has strictly more edges than

B

. Prove that there exists an edge of

A

which if included in the edge set of

B

B

will still remain a forest. Graphs are undirected

1

Satisfy edges as much as possible

k

colors and we have to assign a single color to every vertex. An edge is satisfied if the vertices on that edge, are of different colors.
[*]Prove that you can always find an algorithm which assigns colors to vertices so that at least

\frac{k - 1}{k}|E|

edges are satisfied where

|E|

is the cardinality of the edges in the graph.[/*] [*]Prove that there is a poly time deterministic algorithm for this [/*]