1,360 views
0 0 votes
Let there be two problems $A$ and $B$
It has been proved that,$A<B$ i.e. $A$ is polynomially reducible to $B.$This polynomial
reduction is carried out in time of $O(n).$The problem $B$ can be solved in $O(n^{3})$ time.
what is the time taken to solve problem $'A'?$

$A)O(n)$         $A)O(n^{3})$             $A)O(2^{n})$        $D)$None of these

Please log in or register to answer this question.

Position:
Show:

Related questions

0 0 votes
0 0 answers
633
633 views
commenter commenter asked Jun 13, 2019
633 views
I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like...
4 4 votes
1 answers 1 answer
6.4k
6.4k views
0 0 votes
1 answers 1 answer
1.1k
1.1k views
3 3 votes
1 answers 1 answer
2.1k
2.1k views