smslca
Member level 1
In wikipedia source: https://en.wikipedia.org/wiki/Quadratic_residue
under "composite modulus" section
I found the line
"On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete;however, this is a fixed-parameter tractable problem, where c is the parameter."
what does it mean by "given limit c , and fixed parameter tractable with c as parameter". Does this mean regardless of large values are given for c as a limit , we can solve the quadratic congruence without knowing the factorization? or does it has any other meaning?
what is the limit of c such that we cannot solve quadratic congruence using fpt
If i am wrong or obscure in my question, please notify me.
under "composite modulus" section
I found the line
"On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete;however, this is a fixed-parameter tractable problem, where c is the parameter."
what does it mean by "given limit c , and fixed parameter tractable with c as parameter". Does this mean regardless of large values are given for c as a limit , we can solve the quadratic congruence without knowing the factorization? or does it has any other meaning?
what is the limit of c such that we cannot solve quadratic congruence using fpt
If i am wrong or obscure in my question, please notify me.