recategorized by
1,205 views
1 votes
1 votes

Given the following statements :

$S_{1}$ : The subgraph-isomorphism problem takes two graphs $G_{1}$ and $G_{2}$ and asks whether $G_{1}$ is a subgraph of $G_{2}$ . 

$S_{2}$ : The set-partition problem takes as input a set $S$ of numbers and asks whether the numbers can be partitioned into two sets $A$ and $\bar{A}=S-A$ such that

$\begin{matrix} \sum x & & \sum x \\  & = &  \\ x \in A & & x \in \bar{A} \end{matrix}$

Which of the following is true ?

  1. $S_{1}$ is $NP$ problem and $S_{2}$ is $P$ problem.
  2. $S_{1}$ is $NP$ problem and $S_{2}$ is $NP$ problem. 
  3. $S_{1}$ is $P$ problem and $S_{2}$ is $P$ problem. 
  4. $S_{1}$ is $P$ problem and $S_{2}$ is $NP$ problem. 
recategorized by

1 Answer

0 votes
0 votes

S1is NP problem and S2 is NP problem. 

The subgraph-isomorphism problem is in NP.this can be proved using Clique Theory. Read NP Problems That can be solved using Clique Theory. 
The set partition problem is also on NP. 
Let the certificate y be a subset Y of the set S. The verification algorithm A takes the following steps to verify:
(1) check if every number in Y is a number in S
(2) compute the sum of all numbers in the set Y
(3) computer the set S & Y
(4) compute the sum of all numbers in the set S - Y
(5) compare the two numbers obtained in (2) and (4) to see it these two numbers are identical. If yes, then return yes.

Answer:

Related questions

3 votes
3 votes
2 answers
1
go_editor asked Jan 6, 2017
5,318 views
Four bits are used for packed sequence numbering in a slinding window protocol used in a computer network. What is the maximum window size?481516