Register

CMI2022-A: 10

• edited by
333 views
0 0 votes

What can you conclude from the following statements about problems $\text{A}$ and $\text{B}?$

  1. There is a polynomial-time algorithm to solve $\text {A}$.
  2. There is an exponential-time algorithm to solve $\text{B}$.
  3. $\text{B}$ can be reduced to $\text{A}$ in polynomial-time.

 

  1. Not all of them can be simultaneously true.

  2. There is a polynomial-time algorithm for $\text{B}$.

  3. A cannot be reduced to $\text{B}$ in polynomial-time.

  4. There is no exponential-time algorithm for $\text{A}$.

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · CMI2021-B: 1Next → · CMI2022-A: 9
← Previous in category · CMI2021-B: 1Next in category → · CMI2022-A: 9
Position:
Show:

Related questions

2 2 votes
0 0 answers
529
529 views
admin asked Jul 22, 2022
529 views
CMI2022-A: 1
If Vinay finishes his homework and the school closes early, then he can play in the park or eat an ice cream. He will end up at the dispensary with tummy ache if he eats ...
2 2 votes
2 2 answers
487
487 views
admin asked Jul 22, 2022
487 views
CMI2022-A: 2
There are $n$ members of Chennai Mathematical Institute. Most of them are very studious and like to own lots of books. Now the following facts have been learnt.No two mem...
1 1 vote
0 0 answers
338
338 views
admin asked Jul 22, 2022
338 views
CMI2022-A: 3
Which of the following assertions about regular languages is incorrect?Every subset of a regular language is regular.For every regular language $\text{L}$, there is a sub...
0 0 votes
1 1 answer
394
394 views
admin asked Jul 22, 2022
394 views
CMI2022-A: 4
Consider the following languages over the alphabet $\left \{ a, b, c, d \right \}$$\text{L}_{1} = \left\{ a^{n} b^{n} c^{m} d^{m} \mid n, m\geq 0\right\}$$\text{L}_{2} ...