The Decisional Hardness

How “hard” is NP-hard?

Mort Yao

2016-11-01

(20 Nov 2016) Correction: P ≠ NP is not sufficient to imply that one-way functions exist. See P versus NP problem and one-way functions.


Intro. Starting from November, I’ll summarize my study notes on wiki into weekly blog posts. I always wanted to keep my study progress on track; I feel that it’s hard even to convince myself without visible footprints.

So here we have the first episode. (Hopefully it won’t be the last one)


Asymptotic notation is an important tool in analyzing the time/space efficiency of algorithms.

For decision problems, we now formally define the time complexity classes P and NP, and propose the hardness of NP-complete problems, which plays an indispensable role in the study of algorithm design and modern cryptography.

Computational hardness assumption P ≠ NP. Although it is still an open proposition, many believe that P ≠ NP. Notably, if P ≠ NP holds true,

  1. If a decision problem is polynomial-time unsolvable in general case, we should strive to find approximations or randomized algorithms; exact algorithms cannot be run in worst-case polynomial time thus may not be efficient. This applies to optimization problems too.
  2. One-way functions exist, which implies that pseudorandom generators and functions exist. Consequently, many cryptographic constructions (private-key encryption, MACs, etc.) are provably computationally secure.

(I stand corrected: There is no such a known proof showing that P ≠ NP implies the existence of one-way functions. However, reversely, the existence of one-way functions implies that P ≠ NP. There is an informal argument given by Peter Shor on StackExchange1, rephrased in the section P versus NP problem and one-way functions.)

Later we will cover the notion of security in cryptography, so there is a refresher of basic probability: (Probability is also considerably used in analyzing the behaviors of non-deterministic algorithms, hash functions, etc.)

Plan for next week:

P versus NP problem and one-way functions

Consider the following map: \[f : (x, r) \to s\] where \(x\) is an arbitrary bit string, \(r\) is a string of random bits, and \(s\) is an instance of a \(k\)-SAT problem having \(x\) as a planted solution, while the randomness of \(r\) determines uniquely which \(k\)-SAT problem to choose.

If we can invert the above function \(f\) (in polynomial time), we must already have solved the corresponding \(k\)-SAT problem \(s\) with a planted solution \(x\). \(k\)-SAT problems are known to be NP-complete, and inverting such a function would be as hard as solving a \(k\)-SAT problem with a planted solution, that is, inverting \(f\) at one point can be hard. Clearly, should we have a one-way function, then inverting it is guaranteed to be no easier than inverting \(f\).

So what does it mean if P ≠ NP? We know that \(k\)-SAT problem is hard to solve in its worst case, so function \(f\) can be made as hard to invert as solving a \(k\)-SAT problem in its worst case. However, we don’t know whether it’s possible to have a class \(\mathcal{S}\) of \(k\)-SAT problems with planted solutions that are as hard as general-case \(k\)-SAT problems. If such a class \(\mathcal{S}\) exists, then given any \(s \in \mathcal{S}\), no probabilistic polynomial-time algorithm is able to get \(x\) with a non-negligible probability, so we can conclude that \(f\) is indeed a one-way function. [1]

Problem 1.1. Does there exist a class \(\mathcal{S}\) of \(k\)-SAT problems with planted solutions, such that every \(L \in \mathcal{S}\) is NP-hard?

Conjecture 1.2. If \(\mathrm{P} \neq \mathrm{NP}\), then one-way functions exist.

On the other hand, assume that \(f\) is a one-way function, so that one-way functions do exist, then this implies that \(k\)-SAT problem is hard to solve (in its worse case) by a polynomial-time algorithm, thus we have P ≠ NP. By modus tollens, if P = NP, then no one-way function exists. [2]

Theorem 1.3. If one-way functions exist, then \(\mathrm{P} \neq \mathrm{NP}\).

Proof. (Sketch) Let \(f : \{0,1\}^*\to\{0,1\}^*\) be a one-way function. There is a polynomial-time algorithm \(M_f\) that computes \(y=f(x)\) for all \(x\), thus, there exists a polynomial-time computable circuit that outputs \(y=f(x)\) for all \(x\).

Since \(f\) is a one-way function, that is, for every probabilistic polynomial-time algorithm \(\mathcal{A}\), there is a negligible function \(\mathsf{negl}\) such that \(\Pr[\mathsf{Invert}_{\mathcal{A},f}(n) = 1] \leq \mathsf{negl}(n)\), so we know that no \(\mathcal{A}\) can fully compute \(f^{-1}(x)\) for any given \(x\). \(\mathcal{A}\) fully computes \(f^{-1}\) if and only if it solves the corresponding CIRCUIT-SAT problems of the circuit in all cases. Thus, there must exist some CIRCUIT-SAT problems that cannot be decided by a polynomial-time algorithm, therefore, \(\mathrm{P} \neq \mathrm{NP}\).

Remark 1.4. If one can come up with a construction of the one-way function or a proof that such functions exist, then it holds true that \(\mathrm{P} \neq \mathrm{NP}\).

References and further reading

Books:

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed.

M. Sipser, Introduction to the Theory of Computation, 3rd ed.

J. Katz and Y. Lindell, Introduction to Modern Cryptography, 2nd ed.

Papers:

[1] A. L. Selman, “A survey of one-way functions in complexity theory,” Mathematical Systems Theory, vol. 25, no. 3, pp. 203–221, 1992.

[2] M. Abadi, E. Allender, A. Broder, J. Feigenbaum, and L. A. Hemachandra, “On generating solved instances of computational problems,” in Proceedings on advances in cryptology, 1990, pp. 297–310.


  1. http://cstheory.stackexchange.com/a/8843/21291