Question

What does it mean to say that problem

is a function problem?

is a decision problem?

is in class NP?

is in class P?

Answer 1

In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'.

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values. ... A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem.

A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine. ... A problem is said to be NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem.

The complexity class P is the set of all decision problems that can be solved with worst-case polynomial time-complexity. In other words, a problem is in the class P if it is a decision problem and there exists an algorithm that solves any instance of size n in O(nk) time, for some integer k.