在线名词解释大全
专业、全面、易懂的全领域名词百科

Ifwewanttoproofproblem$Y$canbesolvedinpolynomial-timeviaareductionfromproblem$X$,whichofthefollowingstatementisNOTnecessary?

题型:单选题
选项
A. Arbitrary instances of problem $X$ can be solved in polynomial-time.
B. B.Arbitrary instances of problem $X$ can be solved using polynomial number of calls to oracle that solves problem $Y$.
C. C.Arbitrary instances of problem $Y$ can be solved using polynomial number of calls to oracle that solves problem $X$.
正确答案:B