Proof

The above proof method is called the delayed diagonalization, because the diagonalization requirements and are satisfied by a search process that always halts but the amount of time for the search is not known in advance.

The following theorem, an analog of Post's problem in the classical recursion theory, reveals further structural properties of languages in NP. It can be proved using the technique of delayed diagonalization. We leave its proof as an exercise.

Proof

Following the example , it is easy to see that if , then one-way functions do not exist. Indeed, the complexity of weak one-way functions can be characterized precisely by a subclass UP of NP.

Proof

A one-way function f satisfying the conditions of Definition 4.6 is called a weak one-way function because its inverse is not computable in polynomial time in the very weak worst-case complexity measure. That is, for every polynomial-time computable function g attempting to compute the inverse of f, there are infinitely many instances , such that for all i ≥ 1. However, this function g could be a very good approximation to in the sense that such errors occur only on some very sparsely distributed instances . In the applications of cryptography, a cryptosystem based on such a one-way function is not secure because the approximation function g allows a fast decoding for a large portion of the input instances. Instead, stronger one-way functions whose inverses are hard to compute for the majority of input instances are needed for a secure cryptosystem. We formulate this notion in the following. We only consider functions defined on alphabet {0,1}.

Proof

To see whether the RSA system is a good public-key cryptosystem, we need to verify whether the encryption function is indeed a trapdoor one-way function. First, we observe that if p,q are known, then the integers e and d satisfying (4.1) are easy to find and, hence, the system is easy to set up. To find the pair (e,d), we first select a prime number e between and . As , we have , and so e is relatively prime to . Then, using the Euclidean algorithm, we can find the integer d such that (see, e.g., Knuth (1981)). Next, it is well known that exponentiation function can be computed using modulo multiplications by a simple dynamic programming algorithm. Thus, both E and D are easy to compute. So it is left to determine how hard it is to compute the decryption key from the encryption key (the public key) . If the factors p and q of n are known, then is known and the integer d can be found easily from e. Thus, the security of the RSA system depends on the hardness of factoring an integer into two primes. Conversely, suppose that integer factoring is known to be an intractable problem. Does it mean that the RSA system is secure? In other words, if we have a fast algorithm breaking the RSA system, do we then have a fast factoring algorithm? The answer is yes if we make some modification on the above scheme (see Rabin (1979)). Thus, the complexity of breaking the (modified) RSA system is equivalent to the complexity of factoring the products of two primes, and the RSA system is considered secure, assuming that the function multiplication is a strong one-way function.⁴

4.3 Relativization

The concept of relativization originates from recursive function theory. Consider, for example, the halting problem. We may formulate it in the following form: halts, where M_x is the xth TM in a standard enumeration of all TMs. Now, if we consider all oracle TMs, we may ask whether the set halts is recursive relative to A. This is the halting problem relative to set A. It is easily seen from the original proof for thenonrecursiveness of K that K_A is nonrecursive relative to A (i.e., no oracle TM can decide K_A using A as an oracle). Indeed, most results in recursive function theory can be extended to hold relative to any oracle set. We say that such results relativize. In this section, we investigate the problem of whether in the relativized form. First, we need to define what is meant by relativizing the question of whether . For any set A, recall that P^A (or P(A)) is the class of sets computable in polynomial time by oracle DTMs using A as the oracle and, similarly, NP^A (or ) is the class of sets accepted in polynomial time by oracle NTMs using oracle set A. Using these natural relativized forms of the complexity classes P and NP, we show that the relativized question has both the positive and negative answers, depending on the oracle set A.

Proof

It is interesting to know that the question of whether can be answered either way relative to different oracles. What does this mean to the original unrelativized version of the question of whether P is equal to NP? Much research has been done on this subject, and yet we do not have a consensus. We summarize in the following sections some of the interesting results in this study.

4.4 Unrelativizable Proof Techniques

First, a common view is that the question of whether P is equal to NP is a difficult question in view of Theorem 4.14. As most proof techniques developed in recursion theory, including the basic diagonalization and simulation techniques, relativize, any attack to the question must use a new, unrelativizable proof technique. Many more contradictory relativized results like Theorem 4.14 (including some in Section 4.5) on the relations between complexity classes tend to support this viewpoint. On the other hand, some unrelativizable proof techniques do exist in complexity theory. For instance, we will apply an algebraic technique to collapse the complexity class PSPACE to a subclass IP (see Chapter 10). As there exists an oracle X that separates PSPACE^X from IP^X, this proof is indeedunrelativizable. Though this is a breakthrough in the theory of relativization, it seems still too early to tell whether such techniques are applicable to a wider class of questions.

4.5 Independence Results

One of the most interesting topics in set theory is the study of independence results. A statement A is said to be independent of a theory T if there exist two models M₁ and M₂ of T such that A is true in M₁ and false in M₂. If a statement A is known to be independent of the theory T, then neither A nor its negation is provable in theory T. The phenomenon of contradictory relativized results looks like a mini-independent result: neither the statement nor its negation is provable by relativizable techniques. This observation raises the question of whether they are provable within a formal proof system. In the following, we present a simple argument showing that this is indeed possible.

To prepare for this result, we first briefly review the concept of a formal proof system. An axiomatizable theory is a triple , where Σ is a finite alphabet, is a recursive set of well-formed formulas, and is an r.e. set. The elements in T are called theorems. If T is recursive, we say the theory F is decidable. We are only interested in a sound theory in which we can prove the basic properties of TMs. In other words, we assume that TMs form a submodel for F, all basic properties of TMs are provable in F, and all theorems in F are true in the TM model. In the following, we let be a fixed enumeration of multi-tape DTMs.

Proof

We remark that although the above machine accepts an empty set, this does not imply that the statement is independent of F because the equivalence of and P and the equivalence of and NP are not necessarily provable in the system F. So, the above result proves that for any reasonable formal proof system F, there are some statements of interests to complexity theory that are independent of F. Whether the statement is independent of any specific formal proof system is yet still unknown.