Explain Wikipedia paragraph about primality testing
In computational complexity theory, the formal language corresponding
to the prime numbers is denoted as PRIMES. It is easy to show that
PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can
decide compositeness by nondeterministically guessing a factor.
In 1975, Vaughan Pratt showed that there existed a certificate for
primality that was checkable in polynomial time, and thus that PRIMES
was in NP, and therefore in NP ∩ coNP. See primality certificate for
details.
The subsequent discovery of the Solovay–Strassen and Miller–Rabin
algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm[6]
reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's
result.
The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP
(quasi-polynomial time), which is not known to be comparable with the
classes mentioned above.
Because of its tractability in practice, polynomial-time algorithms
assuming the Riemann hypothesis, and other similar evidence, it was
long suspected but not proven that primality could be solved in
polynomial time. The existence of the AKS primality test finally
settled this long-standing question and placed PRIMES in P. However,
PRIMES is not known to be P-complete, and it is not known whether it
lies in classes lying inside P such as NC or L. It is known that
PRIMES is not in AC0
links for page.
Question: How primality was long suspected to be NP problem? when it can easily check a number is prime or not by checking its divisibility from all number between 1 to n.
time-complexity primes primality-test
edited Jan 18 at 21:37
Will Ness
44.4k468122
asked Jan 18 at 21:28
danikhildanikhil
1
add a comment |
In computational complexity theory, the formal language corresponding
to the prime numbers is denoted as PRIMES. It is easy to show that
PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can
decide compositeness by nondeterministically guessing a factor.
In 1975, Vaughan Pratt showed that there existed a certificate for
primality that was checkable in polynomial time, and thus that PRIMES
was in NP, and therefore in NP ∩ coNP. See primality certificate for
details.
The subsequent discovery of the Solovay–Strassen and Miller–Rabin
algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm[6]
reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's
result.
The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP
(quasi-polynomial time), which is not known to be comparable with the
classes mentioned above.
Because of its tractability in practice, polynomial-time algorithms
assuming the Riemann hypothesis, and other similar evidence, it was
long suspected but not proven that primality could be solved in
polynomial time. The existence of the AKS primality test finally
settled this long-standing question and placed PRIMES in P. However,
PRIMES is not known to be P-complete, and it is not known whether it
lies in classes lying inside P such as NC or L. It is known that
PRIMES is not in AC0
links for page.
Question: How primality was long suspected to be NP problem? when it can easily check a number is prime or not by checking its divisibility from all number between 1 to n.
time-complexity primes primality-test
edited Jan 18 at 21:37
Will Ness
44.4k468122
asked Jan 18 at 21:28
danikhildanikhil
1
1
Complexity for most number-theoretic algorithms include primality testing is expressed in terms of the length of the number, i.e. the number of bit or digits. Therefore you algorithm is exponential in the input size. In other words, if m is the number under consideration, then n = log(m) is the variable we express complexity in terms of.
– James K Polk
Jan 20 at 0:31
add a comment |
In computational complexity theory, the formal language corresponding
to the prime numbers is denoted as PRIMES. It is easy to show that
PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can
decide compositeness by nondeterministically guessing a factor.
In 1975, Vaughan Pratt showed that there existed a certificate for
primality that was checkable in polynomial time, and thus that PRIMES
was in NP, and therefore in NP ∩ coNP. See primality certificate for
details.
The subsequent discovery of the Solovay–Strassen and Miller–Rabin
algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm[6]
reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's
result.
The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP
(quasi-polynomial time), which is not known to be comparable with the
classes mentioned above.
Because of its tractability in practice, polynomial-time algorithms
assuming the Riemann hypothesis, and other similar evidence, it was
long suspected but not proven that primality could be solved in
polynomial time. The existence of the AKS primality test finally
settled this long-standing question and placed PRIMES in P. However,
PRIMES is not known to be P-complete, and it is not known whether it
lies in classes lying inside P such as NC or L. It is known that
PRIMES is not in AC0
links for page.
Question: How primality was long suspected to be NP problem? when it can easily check a number is prime or not by checking its divisibility from all number between 1 to n.
time-complexity primes primality-test
edited Jan 18 at 21:37
Will Ness
44.4k468122
asked Jan 18 at 21:28
danikhildanikhil
1
In computational complexity theory, the formal language corresponding
to the prime numbers is denoted as PRIMES. It is easy to show that
PRIMES is in Co-NP: its complement COMPOSITES is in NP because one can
decide compositeness by nondeterministically guessing a factor.
In 1975, Vaughan Pratt showed that there existed a certificate for
primality that was checkable in polynomial time, and thus that PRIMES
was in NP, and therefore in NP ∩ coNP. See primality certificate for
details.
The subsequent discovery of the Solovay–Strassen and Miller–Rabin
algorithms put PRIMES in coRP. In 1992, the Adleman–Huang algorithm[6]
reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's
result.
The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP
(quasi-polynomial time), which is not known to be comparable with the
classes mentioned above.
Because of its tractability in practice, polynomial-time algorithms
assuming the Riemann hypothesis, and other similar evidence, it was
long suspected but not proven that primality could be solved in
polynomial time. The existence of the AKS primality test finally
settled this long-standing question and placed PRIMES in P. However,
PRIMES is not known to be P-complete, and it is not known whether it
lies in classes lying inside P such as NC or L. It is known that
PRIMES is not in AC0
links for page.
Question: How primality was long suspected to be NP problem? when it can easily check a number is prime or not by checking its divisibility from all number between 1 to n.
time-complexity primes primality-test
time-complexity primes primality-test
edited Jan 18 at 21:37
Will Ness
44.4k468122
asked Jan 18 at 21:28
danikhildanikhil
1
edited Jan 18 at 21:37
Will Ness
44.4k468122
asked Jan 18 at 21:28
danikhildanikhil
1
edited Jan 18 at 21:37
Will Ness
44.4k468122
edited Jan 18 at 21:37
Will Ness
44.4k468122
edited Jan 18 at 21:37
Will Ness
44.4k468122
44.4k468122
asked Jan 18 at 21:28
danikhildanikhil
1
asked Jan 18 at 21:28
danikhildanikhil
1
asked Jan 18 at 21:28
danikhildanikhil
1
1
1
Complexity for most number-theoretic algorithms include primality testing is expressed in terms of the length of the number, i.e. the number of bit or digits. Therefore you algorithm is exponential in the input size. In other words, if m is the number under consideration, then n = log(m) is the variable we express complexity in terms of.
– James K Polk
Jan 20 at 0:31
add a comment |
1
Complexity for most number-theoretic algorithms include primality testing is expressed in terms of the length of the number, i.e. the number of bit or digits. Therefore you algorithm is exponential in the input size. In other words, if m is the number under consideration, then n = log(m) is the variable we express complexity in terms of.
– James K Polk
Jan 20 at 0:31
1
1
Complexity for most number-theoretic algorithms include primality testing is expressed in terms of the length of the number, i.e. the number of bit or digits. Therefore you algorithm is exponential in the input size. In other words, if m is the number under consideration, then n = log(m) is the variable we express complexity in terms of.
– James K Polk
Jan 20 at 0:31
Complexity for most number-theoretic algorithms include primality testing is expressed in terms of the length of the number, i.e. the number of bit or digits. Therefore you algorithm is exponential in the input size. In other words, if m is the number under consideration, then n = log(m) is the variable we express complexity in terms of.
– James K Polk
Jan 20 at 0:31
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54261647%2fexplain-wikipedia-paragraph-about-primality-testing%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54261647%2fexplain-wikipedia-paragraph-about-primality-testing%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Complexity for most number-theoretic algorithms include primality testing is expressed in terms of the length of the number, i.e. the number of bit or digits. Therefore you algorithm is exponential in the input size. In other words, if m is the number under consideration, then n = log(m) is the variable we express complexity in terms of.
– James K Polk
Jan 20 at 0:31