Circuit partitions and #P-complete products of inner products

Details Circuit partitions and #P-complete products of inner products Circuit partitions and #P-complete products of inner products

2010-01-13

arxiv.org/abs/1001.2314v1

Computer Science

Computational Complexity

Scientific paper

We present a simple, natural #P-complete problem. Let G be a directed graph, and let k be a positive integer. We define q(G;k) as follows. At each vertex v, we place a k-dimensional complex vector x_v. We take the product, over all edges (u,v), of the inner product . Finally, q(G;k) is the expectation of this product, where the x_v are chosen uniformly and independently from all vectors of norm 1 (or, alternately, from the Gaussian distribution). We show that q(G;k) is proportional to G's cycle partition polynomial, and therefore that it is #P-complete for any k>1.

Affiliated with

Also associated with

No associations

Rating

Circuit partitions and #P-complete products of inner products 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 Circuit partitions and #P-complete products of inner products, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit partitions and #P-complete products of inner products will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-567058