Varieties of CSPs Discrete variables finite domains;size d=O(d")complete assignments e.g.,Boolean CSPs,incl.Boolean satisfiability (NP-complete) infinite domains (integers,strings,etc.) e.g.,job scheduling,variables are start/end days for each job need a constraint language,e.g.,StartJob1+5<Start.Jobs linear constraints solvable,nonlinear undecidable Continuous variables e.g.,start/end times for Hubble Telescope observations linear constraints solvable in poly time by LP methods Chapter 5 7Varieties of CSPs Discrete variables finite domains; size d ⇒ O(dn) complete assignments ♦ e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete) infinite domains (integers, strings, etc.) ♦ e.g., job scheduling, variables are start/end days for each job ♦ need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3 ♦ linear constraints solvable, nonlinear undecidable Continuous variables ♦ e.g., start/end times for Hubble Telescope observations ♦ linear constraints solvable in poly time by LP methods Chapter 5 7