Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree.

Is there a connection between time complexity of $P$ and degree of $f$ and number of monomials in $f$?

  • $\begingroup$ You can encode every problem with arbitrarily large formulae. What are you really asking? $\endgroup$
    – Raphael
    Dec 5 '14 at 11:50
  • $\begingroup$ I think you also need to formalize a bit more carefully what you mean when you say that a problem $P$ is encoded by a formula $f$. Here's one possibility: $P$ takes as input $x$ and returns a single bit (it's a decision problem); we say that $f$ encodes $P$ if $f(x)$ is the correct output on input $x$. Here's another possibility: problem $P$ is, on input $x$, compute the output $y=P(x)$; $f$ encodes $P$ if for all $x$, $f(x,y)=1$ iff $y=P(x)$ [i.e., $f(x,P(x))=1$ and $f(x,y')=0$ for all $y' \ne P(x)$]. What did you have in mind? $\endgroup$
    – D.W.
    Dec 5 '14 at 20:52

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.