Return to Question

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)

Select a known NP-complete problem $L'$ * Describe an algorithm $f$ that transforms $L'$ into $L$

• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )

Prove that also $f$ runs in polynomial time"

In other words

1. Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving a system of problems q?

Problem q

Given the coefficients $a$, are there any integer solutions for $x$? List them:$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)

Select a known NP-complete problem $L'$ * Describe an algorithm $f$ that transforms $L'$ into $L$

• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )

Prove that also $f$ runs in polynomial time"

In other words

1. Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving a system of problem q?

Problem q

Given the coefficients $a$, are there any integer solutions for $x$? List them:$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)

Select a known NP-complete problem $L'$ * Describe an algorithm $f$ that transforms $L'$ into $L$

• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )

Prove that also $f$ runs in polynomial time"

In other words

1. Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving problem q?

Problem q

Given $a, b, c$ and $N$, are there any integer solutions for $x$ and if so, list them:$$x^2a_n +xb_n +c_n = y (mod z), n→N.$$

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)

Select a known NP-complete problem $L'$ * Describe an algorithm $f$ that transforms $L'$ into $L$

• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )

Prove that also $f$ runs in polynomial time"

In other words

1. Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving a system of problems q?

Problem q

Given the coefficients $a$, are there any integer solutions for $x$? List them:$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)

Select a known NP-complete problem $L'$ * Describe an algorithm $f$ that transforms $L'$ into $L$

• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )

Prove that also $f$ runs in polynomial time"

In other words

1. Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving BOTH Problems 1 & 2?

Problem 1

Given $a, b, c$ and $N$, are there any integer solutions for $x$ and if so, list them:$$x^2a_n +xb_n +c_n = y (mod z), n→N.$$ Problem 2

Given $a$ and $N$, are there any integer solutions for $x$. And if so, list them: $$x^{N}a+x^{N-1}a+...x^1a+x^0a= y (mod z)$$

How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?. But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

• Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)

Select a known NP-complete problem $L'$ * Describe an algorithm $f$ that transforms $L'$ into $L$

• Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )

Prove that also $f$ runs in polynomial time"

In other words

1. Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving problem q?

Problem q

Given $a, b, c$ and $N$, are there any integer solutions for $x$ and if so, list them:$$x^2a_n +xb_n +c_n = y (mod z), n→N.$$