How can integer factorization be classified as an NP problem if it is not a decision yes or no problem but rather a search problem?

[cirosantilli]

EDIT: Publishing a final answer at: https://cs.stackexchange.com/questions/9664/is-it-necessary-for-np-problems-to-be-decision-problems/128702#128702

The Wikipedia page of NP completeness, and many other sources I've looking into, seems to define NP completeness only for decision problems, i.e. problems for which the solution is either yes or no, or in other words: the output of the Turing machine is one bit long. For example: are two graphs isomorphic? has a yes/no answer, and is classified in that page as NP:

The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known (and, if P ≠ NP, disjoint) subsets: P and NP-complete.

However, other sources, such as the integer factorization wiki page also classify this problem as NP:

The problem is clearly in class NP but has not been proved to be or not be NP-complete. It is generally suspected not to be NP-complete.

But what I don't understand is: integer factorization is not a decision problem itself, but rather what some would classify as a "search problem" since the output is multiple integers, and therefore more than 1 yes or no bit.

Or alternatively: is there any fundamental reason why we don't just extend the definition of NP completeness to: "given the answer to an instance and the instance, can you verify it in polynomial time", regardless of whether the answer is one bit or more? Why do we care about the one bit thing at all in practical terms?

I have also been pointed to the FNP complexity class at: https://stackoverflow.com/questions/40773886/what-are-np-intermediate-problems#comment111064899_40773945 So is that the more correct classification of integer factorization, and is saying that integer factorization is NP just not strictly correct? This appears to be the case, the wiki page clarifies a bit more down below:

When discussing what complexity classes the integer factorization problem falls into, it is necessary to distinguish two slightly different versions of the problem:

• The function problem version: given an integer N, find an integer d with 1 < d < N that divides N (or conclude that N is prime). This problem is trivially in FNP, and it is not known whether it lies in FP or not. This is the version solved by practical implementations.
• The decision problem version: given an integer N and an integer M with 1 < M < N, does N have a factor d with 1 < d ≤ M? This version is useful because most well studied complexity classes are defined as classes of decision problems, not function problems.

linking to https://en.wikipedia.org/wiki/Function_problem

I think that https://cseweb.ucsd.edu/~mihir/cse200/decision-search.pdf "4 Decision vs Search for NP-complete languages" is saying that for NP-complete problems, the having a P solution to the decision problem (e.g. "is there a solution to this SAT problem?") implies that you can get a P solution to the search problem as well by breaking up the larger problem into smaller ones and asking the decision problem on smaller versions (easy to prove for SAT as done at "2 Self-reducibility of SAT"). This could explain why the label NP gets loosely applied both decision and search versions of NP-complete problems.

However, as shown on the integer factorization wiki page, we don't know yet if integer factorization is NP-complete or not, and it is is suspected that it isn't. And, to make matters worse, we already have a P algorithm for the decision version of the problem (can this integer be factored) via the AKS primality test. So in this case, decision vs search could really matter if we force the definition of NP to be only for decision problems: https://cs.stackexchange.com/questions/50767/why-is-not-known-whether-integer-factorization-can-be-done-in-polynomial-time-kn So maybe this is why we need to split NP from FNP: they are only equal in case P = NP.

As an interesting related fact, this page: https://blog.computationalcomplexity.org/2019/01/search-versus-decision.html claims without proof that graph isomorphism search (find the isomorphism) can solved efficiently if you had a P decision oracle. So sometimes, problem structure does seem to imply that efficient decision implies efficient search, even if we are not NP-complete (supposing graph isomorphism is truly not NP-complete). Though this does not seem to always be the case (e.g. so far with integer factorization).

Some related question:

• https://cs.stackexchange.com/questions/9664/is-it-necessary-for-np-problems-to-be-decision-problems is a bit similar to my question, not sure if they are equivalent, but hopefully I've provided more motivation to my doubts at the very least
• https://cs.stackexchange.com/questions/473/decision-problems-vs-real-problems-that-arent-yes-or-no and https://cs.stackexchange.com/questions/939/optimization-version-of-decision-problems are talking about optimization and NP-hard problems, which are not the case of integer factorization
• https://cs.stackexchange.com/questions/9556/what-is-the-definition-of-p-np-np-complete-and-np-hard is just too generic
• https://cstheory.stackexchange.com/questions/20930/why-are-so-few-natural-candidates-for-np-intermediate-status is also of interest since we are essentially talking about NP intermediate problems
• https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete says "Since integer factorization is known to be in both NP and co-NP, a proof that it is NP-complete would imply NP = co-NP, which is considered highly unlikely." Hmm, so I understood something wrong in the above, it does not seem to imply that P = NP?
• https://cstheory.stackexchange.com/questions/37812/what-exactly-are-the-classes-fp-fnp-and-tfnp we should answer that really well at some point with examples

[cirosantilli]

Some ideas:

• maybe the main reason is that having a yes no answer generates a formal language, i.e. set of accepted inputs, which is a concept widely used throughout computer science

• as shown on the wiki https://en.wikipedia.org/wiki/Integer_factorization the integer factorization problem does have an associated decision problem to which the search problem can be reduced in polynomial time.

  But that problem it is not the primality test, that is not enough. The associated problem is rather "The decision problem version: given an integer N and an integer M with 1 < M < N, does N have a factor d with 1 < d ≤ M? This version is useful because most well studied complexity classes are defined as classes of decision problems, not function problems."

  So it takes this extra M as input. If M is larger than sqrt N, then we just have the primality test. But for smaller N, we can bisect down the smallest factor (sqrt(N) recuces number of bits by half), then the next one.

  This more complex decision problem, unlike the primality test however, is not known to be in P like the primality test.

  So there are two possible decision problems that could be associated to a given search problem.

  So why do they say that NP-complete problems the search and decision are always equivalent? What is the unique way that you go from search to decision in those cases that makes them always work?

  Every NP problem has a natural associated search problem: given the instance and a verifier turing machine, return (hasproof, proof) such that proof works for the verifier.

• TODO can't we then reduce every search problem to a decision problem in the same way as integer factorization? I.e. use a bisection oracle in the exact same way. Therefore, although this type of reduction does allow you to phrase all NFP problems as NP problems, it is kind of useless.

• the bisection oracle is also a bit ugly as it takes some extra random integer as input. It would be nicer to restrict it to decision problems that take just the input.

• every FNP problem that is not in TFNP leads to a corresponding decision problem of "has a proof or not", this is the natural way to link the two.

  We could rephrase PRIMES as "return a list of numbers with at least one element such that those numbers multiplied give N".

  Then the associated decision problem comes down to a primality test, which we know is P.

• https://www.cs.rochester.edu/~lane/=companion/self-reducible.pdf also talks about decision vs search and self-reducibility

  Would it not also prove that P=NP? Because you can reduce all NP-complete problems to their associated search problems in polynomial time. And primality is the decision problem for the factoring problem "given N return a list of integers >1 <N such that they multiply to N". And we have a P algorithm for primality with AKS primality test. Related: cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf last paragraph and cseweb.ucsd.edu/~mihir/cse200/decision-search.pdf (they do not state this directly, I might be wrong).

  I think not because the theorem there says the decision problem must be NP-complete. But the decision problem is P.