Holant Problems for Regular Graphs with Complex Edge Functions

Details Holant Problems for Regular Graphs with Complex Edge Functions Holant Problems for Regular Graphs with Complex Edge Functions

2010-01-04

arxiv.org/abs/1001.0464v3

Computer Science

Computational Complexity

19 pages, 4 figures, added proofs for full version

Scientific paper

We prove a complexity dichotomy theorem for Holant Problems on 3-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets in combination succeed in proving #P-hardness; and (3) algebraic symmetrization, which significantly lowers the symbolic complexity of the proof for computational complexity. With holographic reductions the classification theorem also applies to problems beyond the basic model.

Affiliated with

Also associated with

No associations

Rating

Holant Problems for Regular Graphs with Complex Edge Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Holant Problems for Regular Graphs with Complex Edge Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Holant Problems for Regular Graphs with Complex Edge Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6850