2
$\begingroup$
  1. Can there be a $P$ algorithm to decide if number of perfect matchings is at least $(n!/2)+1$ for a bipartite graph on $n+n$ vertices?

  2. Can there be a $P$ algorithm to decide if number of witnesses exactly $2^n$ for a $SAT$ formula with $2n$ variables

At least are any of above problems in $PH$? Is there any consequence if they are so?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.