0

I just need some clarification as to what this terminology means in this situation.

A decision problem for $FACTORING$ is as follows.
INPUT: an integer $n$ and a integer $d$
QUESTION: does $n$ have a prime factor less than $d$?

How would $¬FACTORING$ change the question?

Would it change the question to: does $n$ not have a prime factor less than $d$?
Or does $n$ have a prime factor greater than $d$?

MJD
  • 65,394
  • 39
  • 298
  • 580
Takkun
  • 433

1 Answers1

3

What is the complement of the statement "I am wearing a red shirt"? Is it "I am wearing a green shirt"? Or it is "I am not wearing a red shirt"?

MJD
  • 65,394
  • 39
  • 298
  • 580