Skip to main content
edited title
Source Link
Igor Pak
  • 812
  • 5
  • 15

Complexity of permanent evaluationverification

Consider the problem of permanent evaluationverification:

$\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$?

Question: Is it known to be NP-hard? Should one expect this problem to be in C$_{=}$P-complete? (or maybe this is also already known?)

P.S. I might be naive and this is super easy, but excessive googling did not show anything.

Complexity of permanent evaluation

Consider the problem of permanent evaluation:

$\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$?

Question: Is it known to be NP-hard? Should one expect this problem to be in C$_{=}$P-complete? (or maybe this is also already known?)

P.S. I might be naive and this is super easy, but excessive googling did not show anything.

Complexity of permanent verification

Consider the problem of permanent verification:

$\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$?

Question: Is it known to be NP-hard? Should one expect this problem to be in C$_{=}$P-complete? (or maybe this is also already known?)

P.S. I might be naive and this is super easy, but excessive googling did not show anything.

Source Link
Igor Pak
  • 812
  • 5
  • 15

Complexity of permanent evaluation

Consider the problem of permanent evaluation:

$\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$?

Question: Is it known to be NP-hard? Should one expect this problem to be in C$_{=}$P-complete? (or maybe this is also already known?)

P.S. I might be naive and this is super easy, but excessive googling did not show anything.