58 2 The P versus NP Question
puzzles, checking the correctness of a solution is very easy, whereas finding a
solution is sometimes extremely hard.
As was mentioned in the various overviews, it is widely believed that finding
solutions to search problems is, in general, harder than verifying the correctness
of such solutions; that is, it is widely believed that PC \ PF =∅. However, as
also mentioned before, this is only a belief, not a fact. For further discussion
see Section 2.7.
2.3 The Decision Version: Proving versus Verifying
As we shall see in Section 2.4 (and further in Section 3.3), the study of search
problems (e.g., the PC-vs-PF Question) can be “reduced” to the study of deci-
sion problems. Since the latter problems have a less cumbersome terminology,
Complexity Theory tends to focus on them (and maintains its relevance to the
study of search problems via the aforementioned reduction). Thus, the study of
decision problems provides a convenient way for studying search problems. For
example, the study of the complexity of deciding the satisfiability of Boolean
formulae provides a convenient way for studying the complexity of finding
satisfying assignments for such formulae.
We wish to stress, however, that decision problems are interesting and natural
per se (i.e., beyond their role in the study of search problems). After all, some
people do care about the truth, and so determining whether certain claims are
true is a natural computational problem. Specifically, determining whether a
given object (e.g., a Boolean formula) has some predetermined property (e.g.,
is satisfiable) constitutes an appealing computational problem. The P-vs-NP
Question refers to the complexity of solving such problems for a wide and
natural class of properties associated with the class NP. The latter class refers
to properties that have “efficient proof systems” allowing for the verification of
the claim that a given object has a predetermined property (i.e., is a member of
a predetermined set). Jumping ahead, we mention that the P-vs-NP Question
refers to the question of whether properties that have efficient proof systems can
also be decided efficiently (without proofs). Let us clarify all of these notions.
Properties of objects are modeled as subsets of the set of all possible objects
(i.e., a property is associated with the set of objects having this property). For
example, the property of being a prime is associated with the set of prime
numbers, and the property of being connected (resp., having a Hamiltonian
path) is associated with the set of connected (resp., Hamiltonian) graphs. Thus,
we focus on deciding membership in sets (as in Definition 1.2). The standard
formulation of the P-vs-NP Question refers to the questionable equality of