can you explain C option. If there is polynomial time algo for A than there can be polynomial or less than polynomial time algo for B. what is expositional time algo?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+3 votes

We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference?

- If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$
- If the best algorithm for $A$ takes exponential time, then there is no polynomial time algorithm for $B$.
- If we have a polynomial time algorithm for $A$, then we must also have a polynomial time algorithm for $B$
- If we don’t know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.

+3 votes

$A$ is reducible to $B$ implies $B$ is as tough as $A$. ($A$ cannot be harder than $B$)

Option $A$ - False. If $A$ is polynomial then $B$ must be Polynomial ($A$ polynomial algorithm can be easily converted into exponential. Converse is not true).

Option $B$- True. As per first line above, if $A$ is expositional then $B$ cannot be a polynomial time.

Option $C$ - False. If we have polynomial time algorithm for $A$ then we can have polynomial, expositional, sub expositional algorithm for $B$.

Option $D$- False. $A$ can be polynomial. $B$ can be harder than polynomial ( as per first line, $B$ is as hard as $A$ can be termed as $B=\Omega(A)$).

Correct Answer: $B$

Option $A$ - False. If $A$ is polynomial then $B$ must be Polynomial ($A$ polynomial algorithm can be easily converted into exponential. Converse is not true).

Option $B$- True. As per first line above, if $A$ is expositional then $B$ cannot be a polynomial time.

Option $C$ - False. If we have polynomial time algorithm for $A$ then we can have polynomial, expositional, sub expositional algorithm for $B$.

Option $D$- False. $A$ can be polynomial. $B$ can be harder than polynomial ( as per first line, $B$ is as hard as $A$ can be termed as $B=\Omega(A)$).

Correct Answer: $B$

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,833 questions

54,800 answers

189,502 comments

80,723 users