Questions to study Search problems Given an input (e.g.graph,formula,game,..), find a solution(e.g.Hamiltonian path,satisfying assignment,Nash equilibrium,...) Constraint Satisfaction Problem(CSP) Valid solution are those satisfyinga collection of constraintsC.Cm) Allowed operations Difficulty:input is unknown. Allowed operations:solution testing.One can propose candidate solutions If valid:we are told so. Otherwise:an error is signalled. 11
11 • Given an input (e.g. graph, formula, game, …), find a solution (e.g. Hamiltonian path, satisfying assignment, Nash equilibrium, …) Search problems • Valid solution are those satisfying a collection of constraints 𝐶1 ,… ,𝐶𝑚 (, … ) Constraint Satisfaction Problem (CSP) Questions to study • Difficulty: input is unknown. • Allowed operations: solution testing. One can propose candidate solutions • If valid: we are told so. • Otherwise: an error is signalled. Allowed operations
f(x) Input Solution Model CSPA:C1AC2A…nCm(A) space space Trial complexity Verification oracle V Minimum number of queries to V regardless of its computational power D:deterministictrial complexity i:C(s)=0 R:(Las Vegas)randomized trial complexity Algorithm If more than one violations,then V returns anarbitrary one. Worst-case analysis. We usually don't know how Nature returns a violation. We're only given the index i,but not the content of Ci. We usually get an error signal,but don't know the exact reason of the error.(e.g."headache":don't know which ingredients of the reagent cause the problem.) 12
12 Model CSP A: 𝐶1˄𝐶2˄ ∙∙∙ ˄𝐶𝑚(˄ ∙∙∙) 𝑠 ∈ 𝑆 𝑖: 𝐶𝑖 (𝑠) = 0 Input space Solution space Algorithm Verification oracle V 𝑥 𝑓(𝑥) 𝑓 • Minimum number of queries to V • regardless of its computational power • D: deterministic trial complexity • R: (Las Vegas) randomized trial complexity Trial complexity If more than one violations, then V returns an arbitrary one. • Worst-case analysis. • We usually don’t know how Nature returns a violation. We’re only given the index 𝑖, but not the content of 𝐶𝑖 . • We usually get an error signal, but don’t know the exact reason of the error. (e.g. “headache”: don’t know which ingredients of the reagent cause the problem.)