Why was primality test thought to be NP? [duplicate]Primality testing: Why is dividing a number $n$ by every...
Exchange,swap or switch
Pulling the rope with one hand is as heavy as with two hands?
Please, smoke with good manners
US visa is under administrative processing, I need the passport back ASAP
Is there a way to get a compiler for the original B programming language?
How can the Zone of Truth spell be defeated without the caster knowing?
How to stop co-workers from teasing me because I know Russian?
How do I deal with a coworker that keeps asking to make small superficial changes to a report, and it is seriously triggering my anxiety?
How to reduce LED flash rate (frequency)
How exactly does Hawking radiation decrease the mass of black holes?
Stop and Take a Breath!
Realistic Necromancy?
Pass By Reference VS Pass by Value
Does the sign matter for proportionality?
how to sum variables from file in bash
Is there any limitation with Arduino Nano serial communication distance?
Who is the Umpire in this picture?
How would one muzzle a full grown polar bear in the 13th century?
How to get a plain text file version of a CP/M .BAS (M-BASIC) program?
How did Captain America manage to do this?
A Strange Latex Symbol
Why isn't the definition of absolute value applied when squaring a radical containing a variable?
How to solve constants out of the internal energy equation?
French for 'It must be my imagination'?
Why was primality test thought to be NP? [duplicate]
Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?Probabilistic algorithm with two-sided errorWhy is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?Why is FACTOR in Co-NP?Complexity of finding factors of a numberWhy some state that Primes is in NP?Is Mersenne primality testing necessarily EXPTIME?Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?What is the complexity of checking whether $f(x) equiv g(x) hspace{3mm} (text{mod } h(x), n)$?Is finding all primes less than n, doable in polynomial time?Algorithm complexity similar to Selection Sort
$begingroup$
This question already has an answer here:
Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?
2 answers
To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $sqrt{n}$, meaning that the complexity would be $O(sqrt{n})$. In my opinion, $O(sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?
complexity-theory time-complexity np
edited 14 hours ago
David Richerby
71k16109199
asked 17 hours ago
DimenDimen
414
$endgroup$
marked as duplicate by David Richerby, Evil, xskxzr, Discrete lizard♦ 7 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?
2 answers
To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $sqrt{n}$, meaning that the complexity would be $O(sqrt{n})$. In my opinion, $O(sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?
complexity-theory time-complexity np
edited 14 hours ago
David Richerby
71k16109199
asked 17 hours ago
DimenDimen
414
$endgroup$
marked as duplicate by David Richerby, Evil, xskxzr, Discrete lizard♦ 7 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
8
$begingroup$
If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete".
$endgroup$
– John Coleman
14 hours ago
$begingroup$
And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential.
$endgroup$
– gnasher729
11 hours ago
add a comment |
$begingroup$
This question already has an answer here:
Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?
2 answers
To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $sqrt{n}$, meaning that the complexity would be $O(sqrt{n})$. In my opinion, $O(sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?
complexity-theory time-complexity np
edited 14 hours ago
David Richerby
71k16109199
asked 17 hours ago
DimenDimen
414
$endgroup$
This question already has an answer here:
Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?
2 answers
To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $sqrt{n}$, meaning that the complexity would be $O(sqrt{n})$. In my opinion, $O(sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?
This question already has an answer here:
Primality testing: Why is dividing a number $n$ by every integer between 2 and $sqrt{n}$ an inefficient test?
2 answers
complexity-theory time-complexity np
complexity-theory time-complexity np
edited 14 hours ago
David Richerby
71k16109199
asked 17 hours ago
DimenDimen
414
edited 14 hours ago
David Richerby
71k16109199
asked 17 hours ago
DimenDimen
414
edited 14 hours ago
David Richerby
71k16109199
edited 14 hours ago
David Richerby
71k16109199
edited 14 hours ago
David Richerby
71k16109199
71k16109199
asked 17 hours ago
DimenDimen
414
asked 17 hours ago
DimenDimen
414
asked 17 hours ago
DimenDimen
414
414
marked as duplicate by David Richerby, Evil, xskxzr, Discrete lizard♦ 7 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by David Richerby, Evil, xskxzr, Discrete lizard♦ 7 hours ago
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
8
$begingroup$
If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete".
$endgroup$
– John Coleman
14 hours ago
$begingroup$
And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential.
$endgroup$
– gnasher729
11 hours ago
add a comment |
8
$begingroup$
If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete".
$endgroup$
– John Coleman
14 hours ago
$begingroup$
And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential.
$endgroup$
– gnasher729
11 hours ago
8
8
$begingroup$
If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete".
$endgroup$
– John Coleman
14 hours ago
$begingroup$
If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete".
$endgroup$
– John Coleman
14 hours ago
$begingroup$
And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential.
$endgroup$
– gnasher729
11 hours ago
$begingroup$
And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential.
$endgroup$
– gnasher729
11 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.
$bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.
$bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.
Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=log(p)$ and $sqrt{p}=frac{1}{2} log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $sqrt{p}$ will be $2^{frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.
The question "Where exactly does the Primality problem lie" has been answered in the link here
answered 16 hours ago
loxlox
631110
$endgroup$
1
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
add a comment |
$begingroup$
I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.
And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).
answered 11 hours ago
gnasher729gnasher729
12.3k1318
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.
$bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.
$bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.
Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=log(p)$ and $sqrt{p}=frac{1}{2} log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $sqrt{p}$ will be $2^{frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.
The question "Where exactly does the Primality problem lie" has been answered in the link here
answered 16 hours ago
loxlox
631110
$endgroup$
1
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
add a comment |
$begingroup$
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.
$bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.
$bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.
Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=log(p)$ and $sqrt{p}=frac{1}{2} log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $sqrt{p}$ will be $2^{frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.
The question "Where exactly does the Primality problem lie" has been answered in the link here
answered 16 hours ago
loxlox
631110
$endgroup$
1
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
add a comment |
$begingroup$
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.
$bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.
$bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.
Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=log(p)$ and $sqrt{p}=frac{1}{2} log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $sqrt{p}$ will be $2^{frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.
The question "Where exactly does the Primality problem lie" has been answered in the link here
answered 16 hours ago
loxlox
631110
$endgroup$
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.
$bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.
$bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.
Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=log(p)$ and $sqrt{p}=frac{1}{2} log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $sqrt{p}$ will be $2^{frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.
The question "Where exactly does the Primality problem lie" has been answered in the link here
answered 16 hours ago
loxlox
631110
edited 5 hours ago
answered 16 hours ago
loxlox
631110
answered 16 hours ago
loxlox
631110
answered 16 hours ago
loxlox
631110
631110
1
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
add a comment |
1
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
1
1
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
"Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1.
$endgroup$
– gnasher729
14 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
$begingroup$
@gnasher729 thank you for spotting it! I edited it in.
$endgroup$
– lox
13 hours ago
add a comment |
$begingroup$
I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.
And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).
answered 11 hours ago
gnasher729gnasher729
12.3k1318
$endgroup$
add a comment |
$begingroup$
I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.
And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).
answered 11 hours ago
gnasher729gnasher729
12.3k1318
$endgroup$
add a comment |
$begingroup$
I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.
And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).
answered 11 hours ago
gnasher729gnasher729
12.3k1318
$endgroup$
I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.
And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).
answered 11 hours ago
gnasher729gnasher729
12.3k1318
answered 11 hours ago
gnasher729gnasher729
12.3k1318
answered 11 hours ago
gnasher729gnasher729
12.3k1318
answered 11 hours ago
gnasher729gnasher729
12.3k1318
12.3k1318
add a comment |
add a comment |
8
$begingroup$
If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete".
$endgroup$
– John Coleman
14 hours ago
$begingroup$
And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential.
$endgroup$
– gnasher729
11 hours ago