Varieties of CSPs Discrete variables finite domains: n variables,domain size 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.,Startob,+5s StartJoba Continuous variables ■ e.g.,start/end times for Hubble Space Telescope observations linear constraints solvable in polynomial time by linear programming 4Feb2004 CS 3243-Constraint Satisfaction 7 4 Feb 2004 CS 3243 - Constraint Satisfaction 7 Varieties of CSPs ◼ Discrete variables ◼ ◼ finite domains: ◼ n variables, domain size d → O(d n ) 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 ◼ Continuous variables ◼ ◼ e.g., start/end times for Hubble Space Telescope observations ◼ linear constraints solvable in polynomial time by linear programming