Number of divisors of a number - in NP?
$begingroup$
I'm trying to show that the language ${(m,n) | m space text{has exactly} space n space text{divisors}}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime factors of $m.$
2) Verify that $prod i(di+1) = n.$
The problem is that I can't find a way to factorize in polynomial time (in the input) the number $m.$
If stage $1$ takes m steps then it would be $m = 2^{log (m)}$ and the whole algorithm would run in exponential time.
How can I factorize a number in binary in polynomial time (polynomial in the input)?
turing-machines np-complete
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
asked Dec 15 '18 at 8:18
caffeincaffein
11
$endgroup$
|
show 5 more comments
$begingroup$
I'm trying to show that the language ${(m,n) | m space text{has exactly} space n space text{divisors}}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime factors of $m.$
2) Verify that $prod i(di+1) = n.$
The problem is that I can't find a way to factorize in polynomial time (in the input) the number $m.$
If stage $1$ takes m steps then it would be $m = 2^{log (m)}$ and the whole algorithm would run in exponential time.
How can I factorize a number in binary in polynomial time (polynomial in the input)?
turing-machines np-complete
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
asked Dec 15 '18 at 8:18
caffeincaffein
11
$endgroup$
$begingroup$
As far as I know, it is an open problem whether integer factorization is in $P$ or not. No efficient (that is polynomial in time) method is currently known.
$endgroup$
– Peter
Dec 15 '18 at 8:24
$begingroup$
en.wikipedia.org/wiki/…
$endgroup$
– David Peterson
Dec 15 '18 at 8:25
1
$begingroup$
The whole point is that on a non-deterministic turing machine you can guess the correct solution non-deterministically in a single step... you only need to verify it in polynomial time.
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:29
$begingroup$
@spaceisdarkgreen But the problem is that the amount of numbers i need to guess for the correct answer might be polynomial in the size of the binary input. If i have log(m) bits and we have m factors that would be m = 2 ^ (logm) --> exponential
$endgroup$
– caffein
Dec 15 '18 at 8:31
2
$begingroup$
The number of prime factors of $m$ is logarithmic in $m.$ And in any event this has nothing to do with 'factorizing a number in polynomial time', just 'listing the (known) factors in polynomial time'. (Though if the latter were impossible, the former would be trivially impossible, rather than probably impossible, but a hard open question.)
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:53
|
show 5 more comments
$begingroup$
I'm trying to show that the language ${(m,n) | m space text{has exactly} space n space text{divisors}}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime factors of $m.$
2) Verify that $prod i(di+1) = n.$
The problem is that I can't find a way to factorize in polynomial time (in the input) the number $m.$
If stage $1$ takes m steps then it would be $m = 2^{log (m)}$ and the whole algorithm would run in exponential time.
How can I factorize a number in binary in polynomial time (polynomial in the input)?
turing-machines np-complete
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
asked Dec 15 '18 at 8:18
caffeincaffein
11
$endgroup$
I'm trying to show that the language ${(m,n) | m space text{has exactly} space n space text{divisors}}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime factors of $m.$
2) Verify that $prod i(di+1) = n.$
The problem is that I can't find a way to factorize in polynomial time (in the input) the number $m.$
If stage $1$ takes m steps then it would be $m = 2^{log (m)}$ and the whole algorithm would run in exponential time.
How can I factorize a number in binary in polynomial time (polynomial in the input)?
turing-machines np-complete
turing-machines np-complete
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
asked Dec 15 '18 at 8:18
caffeincaffein
11
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
asked Dec 15 '18 at 8:18
caffeincaffein
11
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
edited Dec 15 '18 at 8:39
Gaby Alfonso
1,112317
1,112317
asked Dec 15 '18 at 8:18
caffeincaffein
11
asked Dec 15 '18 at 8:18
caffeincaffein
11
asked Dec 15 '18 at 8:18
caffeincaffein
11
11
$begingroup$
As far as I know, it is an open problem whether integer factorization is in $P$ or not. No efficient (that is polynomial in time) method is currently known.
$endgroup$
– Peter
Dec 15 '18 at 8:24
$begingroup$
en.wikipedia.org/wiki/…
$endgroup$
– David Peterson
Dec 15 '18 at 8:25
1
$begingroup$
The whole point is that on a non-deterministic turing machine you can guess the correct solution non-deterministically in a single step... you only need to verify it in polynomial time.
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:29
$begingroup$
@spaceisdarkgreen But the problem is that the amount of numbers i need to guess for the correct answer might be polynomial in the size of the binary input. If i have log(m) bits and we have m factors that would be m = 2 ^ (logm) --> exponential
$endgroup$
– caffein
Dec 15 '18 at 8:31
2
$begingroup$
The number of prime factors of $m$ is logarithmic in $m.$ And in any event this has nothing to do with 'factorizing a number in polynomial time', just 'listing the (known) factors in polynomial time'. (Though if the latter were impossible, the former would be trivially impossible, rather than probably impossible, but a hard open question.)
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:53
|
show 5 more comments
$begingroup$
As far as I know, it is an open problem whether integer factorization is in $P$ or not. No efficient (that is polynomial in time) method is currently known.
$endgroup$
– Peter
Dec 15 '18 at 8:24
$begingroup$
en.wikipedia.org/wiki/…
$endgroup$
– David Peterson
Dec 15 '18 at 8:25
1
$begingroup$
The whole point is that on a non-deterministic turing machine you can guess the correct solution non-deterministically in a single step... you only need to verify it in polynomial time.
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:29
$begingroup$
@spaceisdarkgreen But the problem is that the amount of numbers i need to guess for the correct answer might be polynomial in the size of the binary input. If i have log(m) bits and we have m factors that would be m = 2 ^ (logm) --> exponential
$endgroup$
– caffein
Dec 15 '18 at 8:31
2
$begingroup$
The number of prime factors of $m$ is logarithmic in $m.$ And in any event this has nothing to do with 'factorizing a number in polynomial time', just 'listing the (known) factors in polynomial time'. (Though if the latter were impossible, the former would be trivially impossible, rather than probably impossible, but a hard open question.)
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:53
$begingroup$
As far as I know, it is an open problem whether integer factorization is in $P$ or not. No efficient (that is polynomial in time) method is currently known.
$endgroup$
– Peter
Dec 15 '18 at 8:24
$begingroup$
As far as I know, it is an open problem whether integer factorization is in $P$ or not. No efficient (that is polynomial in time) method is currently known.
$endgroup$
– Peter
Dec 15 '18 at 8:24
$begingroup$
en.wikipedia.org/wiki/…
$endgroup$
– David Peterson
Dec 15 '18 at 8:25
$begingroup$
en.wikipedia.org/wiki/…
$endgroup$
– David Peterson
Dec 15 '18 at 8:25
1
1
$begingroup$
The whole point is that on a non-deterministic turing machine you can guess the correct solution non-deterministically in a single step... you only need to verify it in polynomial time.
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:29
$begingroup$
The whole point is that on a non-deterministic turing machine you can guess the correct solution non-deterministically in a single step... you only need to verify it in polynomial time.
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:29
$begingroup$
@spaceisdarkgreen But the problem is that the amount of numbers i need to guess for the correct answer might be polynomial in the size of the binary input. If i have log(m) bits and we have m factors that would be m = 2 ^ (logm) --> exponential
$endgroup$
– caffein
Dec 15 '18 at 8:31
$begingroup$
@spaceisdarkgreen But the problem is that the amount of numbers i need to guess for the correct answer might be polynomial in the size of the binary input. If i have log(m) bits and we have m factors that would be m = 2 ^ (logm) --> exponential
$endgroup$
– caffein
Dec 15 '18 at 8:31
2
2
$begingroup$
The number of prime factors of $m$ is logarithmic in $m.$ And in any event this has nothing to do with 'factorizing a number in polynomial time', just 'listing the (known) factors in polynomial time'. (Though if the latter were impossible, the former would be trivially impossible, rather than probably impossible, but a hard open question.)
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:53
$begingroup$
The number of prime factors of $m$ is logarithmic in $m.$ And in any event this has nothing to do with 'factorizing a number in polynomial time', just 'listing the (known) factors in polynomial time'. (Though if the latter were impossible, the former would be trivially impossible, rather than probably impossible, but a hard open question.)
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:53
|
show 5 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3040266%2fnumber-of-divisors-of-a-number-in-np%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 Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3040266%2fnumber-of-divisors-of-a-number-in-np%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
$begingroup$
As far as I know, it is an open problem whether integer factorization is in $P$ or not. No efficient (that is polynomial in time) method is currently known.
$endgroup$
– Peter
Dec 15 '18 at 8:24
$begingroup$
en.wikipedia.org/wiki/…
$endgroup$
– David Peterson
Dec 15 '18 at 8:25
1
$begingroup$
The whole point is that on a non-deterministic turing machine you can guess the correct solution non-deterministically in a single step... you only need to verify it in polynomial time.
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:29
$begingroup$
@spaceisdarkgreen But the problem is that the amount of numbers i need to guess for the correct answer might be polynomial in the size of the binary input. If i have log(m) bits and we have m factors that would be m = 2 ^ (logm) --> exponential
$endgroup$
– caffein
Dec 15 '18 at 8:31
2
$begingroup$
The number of prime factors of $m$ is logarithmic in $m.$ And in any event this has nothing to do with 'factorizing a number in polynomial time', just 'listing the (known) factors in polynomial time'. (Though if the latter were impossible, the former would be trivially impossible, rather than probably impossible, but a hard open question.)
$endgroup$
– spaceisdarkgreen
Dec 15 '18 at 8:53