Mfcttrf

Mathematical cryptic clues

Do any Labour MPs support no-deal?

Email Account under attack (really) - anything I can do?

Why are electrically insulating heatsinks so rare? Is it just cost?

Do VLANs within a subnet need to have their own subnet for router on a stick?

Theorems that impeded progress

Approximately how much travel time was saved by the opening of the Suez Canal in 1869?

Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)

In Japanese, what’s the difference between “Tonari ni” (となりに) and “Tsugi” (つぎ)? When would you use one over the other?

What are these boxed doors outside store fronts in New York?

Show a continuous function with f(x)=y and f(y)=x has a fixed point.

The use of multiple foreign keys on same column in SQL Server

Today is the Center

Why don't electron-positron collisions release infinite energy?

Type 1 Error & Type 2 Error's pregnancy test analogy: is it legit?

Animated Series: Alien black spider robot crashes on Earth

N.B. ligature in Latex

Why are weather verbs 曇る and 晴れる treated differently in this sentence?

How to test if a transaction is standard without spending real money?

Can a Warlock become Neutral Good?

Smoothness of finite-dimensional functional calculus

What is the offset in a seaplane's hull?

Is the language <p,n> belongs to NP class?

How is it possible to have an ability score that is less than 3?

Is the language

belongs to NP class?

Is determining if there is a prime in an interval known to be in P or NP-complete?If the language of a TM is TMs which cannot self recognize, can the original TM?Why is $A_TM$ reducible to $HALT_TM$?Proving a language is not Turing-recognizable by reduction from $D = langle Mrangle mid M text rejects input langle Mrangle$Show that the set of all TMs that move only to the right and loop for some input is decidableProving that a set of grammars for a given finite language is decidableDecidability of the TM's computing a non-empty subset of total functionssmn-theorem: Application by instantiating s<m, n> with other functionUnion of R.E. and Non R.E. languageShow: “Checking no solution for system of linear equations with integer variables and coefficients” $in mathbfNP$Rice's Theorem - usage on $DFA$ or $LBA$

1

$begingroup$

I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:

beginalign
C=leftlangle p,nranglemidright.& left. p text and $n$ are natural numbersright.\
&left.text and there's no prime number in the rangeleft[p,p+nright]right
endalign

could you please check if my reasoning is okay to deduce NP?
(I am not sure, but here's what I think):
for each word $langle p,nrangle in C$ we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between $[p,p+n]$, though I am not really sure it is in NP.

regarding the complement: I think it is in NP because the compliment compositeness can be decided by guessing a factor nondeterministically. But again I am not so sure about it and I don't know how to correctly prove and show it.

Would really appreciate your input on that as I am quite unsure and also checked textbooks and internet (and this site) about it.

Edit: for the sake of solving the problem, due to xskxzr's comment, let's assume p and n are represented by binary, as there's a difference according to his comment between p and n being represented in unary and binary(this is also quite interesting).

complexity-theory turing-machines computability np decision-problem

share|cite|improve this question

edited 1 hour ago

hps13

asked 3 hours ago

hps13hps13

205

New contributor

hps13 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It may depend on how $p$ and $n$ are represented (by unary or binary).
  $endgroup$
  – xskxzr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Possible duplicate of Is determining if there is a prime in an interval known to be in P or NP-complete?
  $endgroup$
  – xskxzr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My question is about: 1) is my reasoning is enough/correct to deduce C being NP class? 2)regarding its complimentary(which is not written in the aforementioned link - they don't deal with it). those are 2 different questions and i would appreciate learning from my problem in order to understand my mistake and additionally if the compliment of C is in NP
  $endgroup$
  – hps13
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @xskxzr That's not the same question. The OP is asking whether it is in NP, not NP-complete. That question is also the complement of this one.
  $endgroup$
  – orlp
  1 hour ago
  

  
  
  
  

add a comment | 

1

$begingroup$

I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:

beginalign
C=leftlangle p,nranglemidright.& left. p text and $n$ are natural numbersright.\
&left.text and there's no prime number in the rangeleft[p,p+nright]right
endalign

could you please check if my reasoning is okay to deduce NP?
(I am not sure, but here's what I think):
for each word $langle p,nrangle in C$ we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between $[p,p+n]$, though I am not really sure it is in NP.

regarding the complement: I think it is in NP because the compliment compositeness can be decided by guessing a factor nondeterministically. But again I am not so sure about it and I don't know how to correctly prove and show it.

Would really appreciate your input on that as I am quite unsure and also checked textbooks and internet (and this site) about it.

Edit: for the sake of solving the problem, due to xskxzr's comment, let's assume p and n are represented by binary, as there's a difference according to his comment between p and n being represented in unary and binary(this is also quite interesting).

complexity-theory turing-machines computability np decision-problem

share|cite|improve this question

edited 1 hour ago

hps13

asked 3 hours ago

hps13hps13

205

New contributor

hps13 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It may depend on how $p$ and $n$ are represented (by unary or binary).
  $endgroup$
  – xskxzr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Possible duplicate of Is determining if there is a prime in an interval known to be in P or NP-complete?
  $endgroup$
  – xskxzr
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My question is about: 1) is my reasoning is enough/correct to deduce C being NP class? 2)regarding its complimentary(which is not written in the aforementioned link - they don't deal with it). those are 2 different questions and i would appreciate learning from my problem in order to understand my mistake and additionally if the compliment of C is in NP
  $endgroup$
  – hps13
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @xskxzr That's not the same question. The OP is asking whether it is in NP, not NP-complete. That question is also the complement of this one.
  $endgroup$
  – orlp
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:

beginalign
C=leftlangle p,nranglemidright.& left. p text and $n$ are natural numbersright.\
&left.text and there's no prime number in the rangeleft[p,p+nright]right
endalign

could you please check if my reasoning is okay to deduce NP?
(I am not sure, but here's what I think):
for each word $langle p,nrangle in C$ we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between $[p,p+n]$, though I am not really sure it is in NP.

regarding the complement: I think it is in NP because the compliment compositeness can be decided by guessing a factor nondeterministically. But again I am not so sure about it and I don't know how to correctly prove and show it.

Would really appreciate your input on that as I am quite unsure and also checked textbooks and internet (and this site) about it.

Edit: for the sake of solving the problem, due to xskxzr's comment, let's assume p and n are represented by binary, as there's a difference according to his comment between p and n being represented in unary and binary(this is also quite interesting).

complexity-theory turing-machines computability np decision-problem

share|cite|improve this question

edited 1 hour ago

hps13

asked 3 hours ago

hps13hps13

205

New contributor

hps13 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

edited 1 hour ago

hps13

asked 3 hours ago

hps13hps13

205

New contributor

hps13 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

edited 1 hour ago

hps13

asked 3 hours ago

hps13hps13

205

New contributor

hps13 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 3 hours ago

hps13hps13

205

New contributor

hps13 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 3 hours ago

hps13hps13

205

1 Answer
1

active

oldest

votes

2

$begingroup$

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial instance we have $n < p$.

The complement (there exists a prime in range $[p, p+n]$) is quite easy (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q in [p, p+n]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|[p, p+n]| approx |[p, 2p]| approx p approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.

share|cite|improve this answer

answered 2 hours ago

orlporlp

5,9151826

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  thank you very much for your answer. it really helps me understand the background behind the problem, but as you've written, i am trying to check whether it is an NP problem and it is indeed a difficult yet interesting thing. thank you so much for what you've written, it really helps
  $endgroup$
  – hps13
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am wondering - did the explanation i tried to give is wrong? I am not sure, but here's what I think: for each word ⟨p,n⟩∈C we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between [p,p+n],
  $endgroup$
  – hps13
  1 hour ago
  

  
  
  
  

add a comment | 

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: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
);



);

hps13 is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106600%2fis-the-language-p-n-p-and-n-are-natural-numbers-and-theres-no-prime-number%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial instance we have $n < p$.

The complement (there exists a prime in range $[p, p+n]$) is quite easy (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q in [p, p+n]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|[p, p+n]| approx |[p, 2p]| approx p approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.

share|cite|improve this answer

answered 2 hours ago

orlporlp

5,9151826

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  thank you very much for your answer. it really helps me understand the background behind the problem, but as you've written, i am trying to check whether it is an NP problem and it is indeed a difficult yet interesting thing. thank you so much for what you've written, it really helps
  $endgroup$
  – hps13
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am wondering - did the explanation i tried to give is wrong? I am not sure, but here's what I think: for each word ⟨p,n⟩∈C we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between [p,p+n],
  $endgroup$
  – hps13
  1 hour ago
  

  
  
  
  

add a comment | 

2

$begingroup$

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial instance we have $n < p$.

The complement (there exists a prime in range $[p, p+n]$) is quite easy (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q in [p, p+n]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|[p, p+n]| approx |[p, 2p]| approx p approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.

share|cite|improve this answer

answered 2 hours ago

orlporlp

5,9151826

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  thank you very much for your answer. it really helps me understand the background behind the problem, but as you've written, i am trying to check whether it is an NP problem and it is indeed a difficult yet interesting thing. thank you so much for what you've written, it really helps
  $endgroup$
  – hps13
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am wondering - did the explanation i tried to give is wrong? I am not sure, but here's what I think: for each word ⟨p,n⟩∈C we know that the word belongs to C because there exists a primal certificate - an nontrivial divisor to any of the numbers between [p,p+n],
  $endgroup$
  – hps13
  1 hour ago
  

  
  
  
  

add a comment | 

$begingroup$

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial instance we have $n < p$.

The complement (there exists a prime in range $[p, p+n]$) is quite easy (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q in [p, p+n]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|[p, p+n]| approx |[p, 2p]| approx p approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.

share|cite|improve this answer

answered 2 hours ago

orlporlp

5,9151826

$endgroup$

share|cite|improve this answer

answered 2 hours ago

orlporlp

5,9151826

answered 2 hours ago

orlporlp

5,9151826

answered 2 hours ago

orlporlp

5,9151826