P vs. NP,algorithm

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
4
down vote

favorite












Is there a known, explicit example of an algortihm with the property such that if $Pneq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?










share|cite|improve this question

















  • 1




    Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/…
    – Emil Jeřábek
    2 hours ago














up vote
4
down vote

favorite












Is there a known, explicit example of an algortihm with the property such that if $Pneq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?










share|cite|improve this question

















  • 1




    Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/…
    – Emil Jeřábek
    2 hours ago












up vote
4
down vote

favorite









up vote
4
down vote

favorite











Is there a known, explicit example of an algortihm with the property such that if $Pneq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?










share|cite|improve this question













Is there a known, explicit example of an algortihm with the property such that if $Pneq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?







ds.algorithms np p-vs-np






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 3 hours ago









user2925716

1375




1375







  • 1




    Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/…
    – Emil Jeřábek
    2 hours ago












  • 1




    Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/…
    – Emil Jeřábek
    2 hours ago







1




1




Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/…
– Emil Jeřábek
2 hours ago




Sort of. If P = NP, Levin’s universal search algorithm runs in polynomial time on accepting instances en.wikipedia.org/wiki/…
– Emil Jeřábek
2 hours ago










1 Answer
1






active

oldest

votes

















up vote
3
down vote



accepted










If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:



Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject





share|cite|improve this answer






















  • How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
    – user2925716
    2 hours ago










  • @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
    – Marzio De Biasi
    1 hour ago










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: "114"
;
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',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41751%2fp-vs-np-algorithm%23new-answer', 'question_page');

);

Post as a guest






























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
3
down vote



accepted










If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:



Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject





share|cite|improve this answer






















  • How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
    – user2925716
    2 hours ago










  • @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
    – Marzio De Biasi
    1 hour ago














up vote
3
down vote



accepted










If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:



Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject





share|cite|improve this answer






















  • How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
    – user2925716
    2 hours ago










  • @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
    – Marzio De Biasi
    1 hour ago












up vote
3
down vote



accepted







up vote
3
down vote



accepted






If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:



Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject





share|cite|improve this answer














If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:



Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject






share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 11 mins ago

























answered 2 hours ago









Marzio De Biasi

18k240108




18k240108











  • How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
    – user2925716
    2 hours ago










  • @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
    – Marzio De Biasi
    1 hour ago
















  • How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
    – user2925716
    2 hours ago










  • @user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
    – Marzio De Biasi
    1 hour ago















How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
– user2925716
2 hours ago




How do I quicly decide if "I is a valid encoding of a proof of P = NP in PA (or ZFC)" ?
– user2925716
2 hours ago












@user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
– Marzio De Biasi
1 hour ago




@user2925716 You can do it in polynomial time (imagine that $I$ is a string that represents the full proof in any reasonable deduction system).
– Marzio De Biasi
1 hour ago

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41751%2fp-vs-np-algorithm%23new-answer', 'question_page');

);

Post as a guest













































































Comments

Popular posts from this blog

What does second last employer means? [closed]

Installing NextGIS Connect into QGIS 3?

One-line joke