recategorized by
957 views
4 votes
4 votes

$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices).
 Define the following two languages.

$\text{SCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$
        and
$\text{LCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at least k}\}$

Which of the following is NOT known to be TRUE (to the best of our current knowledge) ?

  1. $\text{SCYCLE} \in P$
  2. $\text{LCYCLE} \in NP.$
  3. $\text{LCYCLE} \leq_{p} \text{SCYCLE}$ (i.e, there is a polynomial time many-to -one reduction
     from $\text{LCYCLE}$ to $\text{SCYCLE}$).
  4. $\text{LCYCLE}$ is NP-complete.
  5. $\text{SCYCLE} \leq_{p} \text{LCYCLE}$ (i.e, there is a polynomial time many-to-one reduction
    from $\text{SCYCLE}$ to $\text{LCYCLE}$).
recategorized by

1 Answer

1 votes
1 votes
L cycle problem can be reducible to finding Hamiltonian cycle which is np complete

Where as S Cycle is an class P problem

So 3 in directly ask us P=NP which is not known
Answer:

Related questions

3 votes
3 votes
1 answer
1
go_editor asked Dec 28, 2016
613 views
Assume $P \neq NP$. Which of the following is not TRUE?$2$-SAT in NP$2$-SAT in coNP$3$-SAT is polynmial-time reducible to $2$-SAT4-SAT is polynmial-time reducible to $3$-...
2 votes
2 votes
1 answer
3