Score:0

Is the kind of definition and analysis of hardness of a problem, using "experiment", standard to complexity analysis of problems?

in flag
Tim

In Katz's Introduction to Modern Cryptography, there are several hard problems, and for each problem, there is an experiment, where an algorithm generates a problem instance, and another algorithm solves the problem instance. For example, consider the discrete-logarithm problem in 9.3.2:

Let GG be a group generating algorithm which for each n, generates (G,q,p).

Let A be an algorithm for solving the problem.

The discrete-logarithm experiment DLog_{A,GG} (n):

  1. Run GG(1^n ) to obtain (G , q, g), where G is a cyclic group of order q (with kqk = n), and g is a generator of G .
  2. Choose a uniform h in G .
  3. A is given G , q, g, h, and outputs x in Z_q .
  4. The output of the experiment is defined to be 1 if g^x = h, and 0 otherwise.

DEFINITION 9.63 We say the discrete-logarithm problem is hard relative to GG if for all probabilistic polynomial-time algorithms A there exists a negligible function negl such that Pr[DLog A,GG(n) = 1] = negl(n).

Is that kind of definition and analysis of hardness of a problem, involving the concept of "experiment", standard to complexity analysis of problems in general (not just in cryptography)?

Do books on complexity analysis of problems use this kind of definition and analysis of hardness of a problem?

Thanks.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.