0
$\begingroup$

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$?

1 Answers 1

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"?