Reference no: EM132816665

Question 1. Let A, B, C  ⊆ {0, 1}* with C ≠ {0, 1}*. The tagged union of A and B is the language

A⊕B= 0A U 1B = {0x|x  ∈ A} ∪ {1x|x ∈ B}.

Prove: If A ≤ ^p_m C and B ≤ ^p_m C, then A⊕B ≤ ^p_m C.

Question 2. The complexity class PP consists of all languages A for which there exist a polynomial q and a language B ∈ P such that for all x ∈ {0, 1}*,
,
x ∈ A <=> Prob  [<x, w> ∈ B] > 1/2
              w∈{0,1}q(|x|)

where the probability is computed according to the uniform distribution on {0, 1}^q(|w|).

Prove: NP ⊆ PP ⊆ PSPACE.

Question 3. In this problem we'll show that there is an EXP-complete language in E. The exponential-time halting problem is
K_EXP = {(w,x, 0^t) M_w, accepts x and time m_w(x) ≤ 2^t.
(a) Prove that KExp ∈ E.
(b) Prove that KExp is EXP-complete.
(c) Prove the following.

i.K_Exp ∈/ P

ii.K_Exp ∈ PSPACE if and only if EP = PSPACE.

Question 4. This problem concerns multivariate polynomials with integer coefficients. An example is

p(x₁, x₂, x₃) = x₁ .(1 - x₂).x₃ + x₂.x₃ - 3x₂2x₃.

We say that a multivariate polynomial p (x₁,.....x_n) has a 0-1 solution if there exist b₁,......b_n ∈ {0, 1} such that p(b₁,.......,b_n) =0.

Let

0-1-MPOLY = { p(x₁,.......x_n)|p(x₁,......x_n) is a multivariate polynomial with a 0-1 solution}

                                       | polynomial with a 0-1 Solution}

Prove that 0-1-MPOLY is NP-complete.

Question 5. In the multi-processor scheduling problem we are given the following.
• m processors
• a collection of n jobs
• the number of seconds tin required for a processor to complete each job j
• a target deadline of d seconds

Each job must be scheduled on a processor and allowed to run to completion. The jobs are all independent; they can be scheduled concurrently and in any order. The goal is to determine if there is a way to schedule the jobs on the processors so that all the jobs are processed within d seconds. More formally, the question is to determine if there is a way to partition the collection of jobs J = {1, ... n} into m sets J₁,.....J_m to be run on each of the m processors such that for each processor i, 1 ≤ i ≤ m, the total time

∑_j∈Ji t(j)

used is at most d.

Let MP-SCHED be the set of all (m, n, t(1), t(n), d) such that the collection of all n jobs can be completed within d seconds on m processors as described above.

Prove that MP-SCHED is NP-complete.

Attachment:- scheduling problem.rar