Computational complexity conjecture for the alpha-permanent
Statement
Let be a matrix and let denote its alpha-permanent. For a positive integer , the notation refers to the relevant counting-complexity class, and to deterministic polynomial time.
Computational complexity conjecture. Computation of the -permanent is -complete, except for
for some . The complexity for lies somewhere between and and is monotonically non-decreasing as decreases.
The paper notes that the computational complexity of the alpha-permanent had not been studied and leaves open the possibility that , in which case only is exceptional. The authors further identify the central expectation as -completeness unless is a negative integer.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.