|
Friday, June 19, 2009 |
|
|
|
|
Computational Complexity of Translationally-Invariant Systems |
|
|
In general, it is a computationally hard problem to determine whether a
two-dimensional grid can be tiled using some set of rules on what kinds
of tiles can be adjacent. A related problem, hard for a quantum
complexity class, is to determine the lowest energy state of a system
with interactions only for particles adjacent along a line. Of course,
there are also specific systems of this type which are easy to solve.
What are the key distinguishing properties between the hard systems and
the easy systems? One might expect that symmetry should play a role,
with very symmetric systems being easy. However, we show that even with
a great deal of symmetry - translational invariance - tiling problems
and spin systems remain hard to solve in general. |