Problem = (n,k) Solution = binary decision tree valid: has n+1 leaves labeled 0, 1, ... n. ... quality: depth of decision tree / n

Problem = (n0,C) Solution = n valid: n>n0 quality: irrelevant

Problem = indirected graph G = (V,E) Solution = subset S of V valid: S is independent set quality: |S|/|V|

Problem = X Solution = Y valid: y in Y(x)? quality: irrelevant## Claim(Domain)

A claim in domain D is a 4-tuple: (setOfProblems,q,r,protocol), where setOfProblems is a subset of D.Problem, q in [0,1] is a quality and r is a positive integer representing some resource.A protocol consists of a data gathering algorithm involving Alice and Bob and a predicate that determines the outcome of the refutation protocol. The data gathering algorithm is of the form (Alice (data) Bob(data))+ or (Bob(data) Alice(data))+. The predicate gets all the data for evaluation. We distinguish between defense and refutation predicates. Alice always makes the claim and Bob tries to refute.

## HSR

## positive: HSR(n,k) <= q

setOfProblems = (n,k) (singleton) q = number of questions needed protocol: Bob((n,k)) Alice(decision tree DT for n,k) defense = valid((n,k),DT) and depth(DT) <= q/n## negative: HSR(n,k) > q

setOfProblems = (n,k) (singleton) q = number of questions needed r = irrelevant protocol: Alice((n,k)) Bob(decision tree DT for n,k) refutation = valid((n,k),DT) and depth(DT)<= q/n## Landau (O notation)

## positive: f(n) in O(g(n))

Math: Exists n0,C ForAll n>n0: f(n)<=C*g(n)setOfProblems = {(n0,C)} q = irrelevant protocol: Alice(n0,C)) Bob(n) defense = n>n0 and f(n) <= C*g(n)## negative: f(n) !in O(g(n))

Math: ForAll n0,C Exists n>n0: f(n) > C*g(n)setOfProblems = {(n0,C)} q = irrelevant protocol: Bob (n0,C)) Alice(n) refutation = n>n0 and f(n) <= C*g(n) Exercises: HSR(n,2) in O(n) HSR(n,2) not in O(log(n)) HSR(n,2) in O(n^(1/2)) n^(1/2) not in O(log(n))## Independent Set

## positive: Bob can efficiently approximate Alice' solution within 0.9.

Approximate secret solution.setOfProblems = {G=(V,E)} q = 0.9 of secret solution r = running-time <= |E|^2 protocol: Alice (G=(V,E),secret sA = Alice' solution) Bob(sB = Bob's solution) defense = |sB|/|sA| >= 0.9## Protocol Negation