Ian Payne, Pure Mathematics, University of Waterloo
"Bounded Width and the Local Consistency Algorithm: Part 1"
I
will
define
what
it
means
for
a
relational
structure
$\mathbb{A}$
to
have
bounded
width,
and
explain
why
such
structures
are
important.
To
do
this,
the
local
consistency
algorithm
has
to
be
explained,
which
requires
several
definitions
about
relational
structures.
The
actual
definition
of
bounded
width
may
spill
into
part
2.
It
is
well
known
to
people
who
already
understand
all
of
the
words
in
this
abstract
that
if
$\mathbb{A}$
has
bounded
width,
then
the
decision
problem
CSP$(\mathbb{A})$
is
in
$P$.
My
goal
is
to
prove
this
fact,
and
expand
the
aforementioned
group
of
people.