Consider an equations of the form: (a + x) * (b + y) - c = 0 Or: (a + x) * (b + y) = c Or: x * y = c

Classifier evaluates these equations as binary quadratic type. Are they can be solved only for exponential time? Or there is another way?

  • $\begingroup$ Here is a simple $O(c)$ algorithm: iterate on $x$ from $1$ to $c$ and check whether $\frac{c}{x}\in \mathbb{N}$. For every $x$ such that $\frac{c}{x}\in\mathbb{N}$, choose $y=\frac{c}{x}$ and it will be a valid solution. $\endgroup$
    – nir shahar
    Jul 20 at 9:47
  • $\begingroup$ Please define precisely the class of equations. Three examples is not a substitute for a general specification of the problem you want to solve. What do you mean by "solve"? Do you want to know whether there exists any integer solution? Do you want to output one integer solution? Do you want to enumerate all integer solutions? Please edit your question to state the problem precisely. Often a good way to do that is to list the input (in general form) and the desired output. $\endgroup$
    – D.W.
    Jul 20 at 18:55

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.