Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,819 questions
Filter by
Sorted by
Tagged with
529 views

Complexity of hex with random turn order.

I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each ...
1k views

True Bit Complexity of matrix multiplication is $O(n^{4})$

Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry ...
1k views

2k views

Consequences of #P = FP

Which would be the consequences of #P = FP? I'm interested in both practical and theoretical consequences. From a practical point of view, I'm particularly interested in consequences on Artificial ...
595 views

When is Ising partition function easy to compute?

Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function $Z$ is easy to compute if $Z$ can be deterministically computed to arbitrary ...
929 views

Limits to Parallel Computing

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject: http://en.wikipedia.org/wiki/NC_%28complexity%29 The ...
250 views