{ localUrl: '../page/arguments_against_P_NP.html', arbitalUrl: 'https://arbital.com/p/arguments_against_P_NP', rawJsonUrl: '../raw/4bf.json', likeableId: '2683', likeableType: 'page', myLikeValue: '0', likeCount: '4', dislikeCount: '0', likeScore: '4', individualLikes: [ 'TsviBT', 'JaimeSevillaMolina', 'EricRogstad', 'FlynSequeira' ], pageId: 'arguments_against_P_NP', edit: '6', editSummary: 'fixed summary formatting; improved wording', prevEdit: '5', currentEdit: '6', wasPublished: 'true', type: 'wiki', title: 'P vs NP: Arguments against P=NP', clickbait: 'Why we believe P and NP are different', textLength: '1644', alias: 'arguments_against_P_NP', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'EricRogstad', editCreatedAt: '2016-07-08 08:15:00', pageCreatorId: 'JaimeSevillaMolina', pageCreatedAt: '2016-06-14 22:22:42', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '4', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '120', text: '[summary:\n\n - Proving $P \\neq NP$ is harder if true than proving $P=NP$ if true.\n - After 50 years we haven't found any efficient algorithm for $NP$-complete problems. \n - The polynomial hierarchy is compared to the arithmetical hierarchy, and the analogy implies $P \\neq NP$\n]\n\n\n\n#Natural proofs\nIf $P \\neq NP,$ then there are results showing that lower bounds in complexity are inherently harder to prove in a [natural_proof technical yet natural sense]. In other words, if $P \\neq NP$ then proving $P \\neq NP$ is hard.\n\nThe opposite proposition for $P=NP$ is also expected to be true. That is, it would make sense that if $P=NP,$ then it should be easier to prove, since we could build far more efficient [ theorem provers].\n\n#Empirical argument\nWe have been trying to get a fast algorithm for [ $NP$-complete] problems since the 70s, without success. And take into account that "we" does not only comprise a minor group of theoretical computer scientists, but a whole industry trying to get faster algorithms for commercial purposes.\n\nOne could also argue more weakly that if $P=NP$, then evolution could have made use of this advantage to sped up its search process, or create more efficient minds to solve $NP$-complete problems at thoughtspeed.\n\n#The arithmetical hierarchy argument\nSome authors have drawn an analogy between the [ polynomial hierarchy] and the [1mg arithmetical hierarchy].\n\nThere are results showing that the [ arithmetical hierarchy is strict], and if the analogy holds then we would have that the polynomial hierarchy is strict as well, [collapse_of_the_polynomial_hierarchy which automatically implies $P \\neq NP$].', metaText: '', isTextLoaded: 'true', isSubscribedToDiscussion: 'false', isSubscribedToUser: 'false', isSubscribedAsMaintainer: 'false', discussionSubscriberCount: '2', maintainerCount: '2', userSubscriberCount: '0', lastVisit: '', hasDraft: 'false', votes: [], voteSummary: 'null', muVoteSummary: '0', voteScaling: '0', currentUserVote: '-2', voteCount: '0', lockedVoteType: '', maxEditEver: '0', redLinkCount: '0', lockedBy: '', lockedUntil: '', nextPageId: '', prevPageId: '', usedAsMastery: 'false', proposalEditNum: '0', permissions: { edit: { has: 'false', reason: 'You don't have domain permission to edit this page' }, proposeEdit: { has: 'true', reason: '' }, delete: { has: 'false', reason: 'You don't have domain permission to delete this page' }, comment: { has: 'false', reason: 'You can't comment in this domain because you are not a member' }, proposeComment: { has: 'true', reason: '' } }, summaries: {}, creatorIds: [ 'JaimeSevillaMolina', 'EricRogstad', 'NateSoares' ], childIds: [], parentIds: [ 'P_vs_NP' ], commentIds: [], questionIds: [], tagIds: [ 'stub_meta_tag' ], relatedIds: [], markIds: [], explanations: [], learnMore: [], requirements: [], subjects: [], lenses: [], lensParentId: 'P_vs_NP', pathPages: [], learnMoreTaughtMap: {}, learnMoreCoveredMap: {}, learnMoreRequiredMap: {}, editHistory: {}, domainSubmissions: {}, answers: [], answerCount: '0', commentCount: '0', newCommentCount: '0', linkedMarkCount: '0', changeLogs: [ { likeableId: '3033', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '16139', pageId: 'arguments_against_P_NP', userId: 'EricRogstad', edit: '6', type: 'newEdit', createdAt: '2016-07-08 08:15:00', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'fixed summary formatting; improved wording' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '16133', pageId: 'arguments_against_P_NP', userId: 'NateSoares', edit: '5', type: 'newEdit', createdAt: '2016-07-08 03:37:13', auxPageId: '', oldSettingsValue: '', newSettingsValue: '!= -> \\neq' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13024', pageId: 'arguments_against_P_NP', userId: 'JaimeSevillaMolina', edit: '0', type: 'newAlias', createdAt: '2016-06-15 11:25:12', auxPageId: '', oldSettingsValue: '4bf', newSettingsValue: 'arguments_against_P_NP' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13020', pageId: 'arguments_against_P_NP', userId: 'JaimeSevillaMolina', edit: '0', type: 'deleteTag', createdAt: '2016-06-15 11:16:06', auxPageId: 'needs_summary_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13018', pageId: 'arguments_against_P_NP', userId: 'JaimeSevillaMolina', edit: '3', type: 'newEdit', createdAt: '2016-06-15 11:13:31', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '12882', pageId: 'arguments_against_P_NP', userId: 'EricRogstad', edit: '2', type: 'newEdit', createdAt: '2016-06-14 23:35:48', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '12859', pageId: 'arguments_against_P_NP', userId: 'EricBruylant', edit: '1', type: 'newTag', createdAt: '2016-06-14 22:41:40', auxPageId: 'needs_summary_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '12825', pageId: 'arguments_against_P_NP', userId: 'JaimeSevillaMolina', edit: '1', type: 'newEdit', createdAt: '2016-06-14 22:22:42', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '12821', pageId: 'arguments_against_P_NP', userId: 'JaimeSevillaMolina', edit: '1', type: 'newTag', createdAt: '2016-06-14 22:22:40', auxPageId: 'stub_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '12809', pageId: 'arguments_against_P_NP', userId: 'JaimeSevillaMolina', edit: '1', type: 'newParent', createdAt: '2016-06-14 22:04:05', auxPageId: 'P_vs_NP', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }