Partitions, the P versus NP problem and applications

Partitions, the P versus NP problem and applications | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Partitions, the P versus NP problem and applications Vassilly Voinov This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6400086/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract A new deterministic polynomial-time algorithm for sets of different positive integers partitioning has been introduced. The most important properties of the algorithm are that its time-complexity is O(nlogn) and that it is invariant w.r.t. the number of elements in a particular part. An implementation of this algorithm and the trivial combinatorial show that the classical Partition and the 4-Partition problem, currently considered to be in the NP-complete and the NP-complete in the strong sense complexity classes, respectively, are both solvable in polynomial time, thus belonging to class P. These results permit to introduce the P-complete class of problems reducible to each other by a polynomial transformation. Since it is a subclass of the NP-complete complexity class, from the well-established theory of NP-completeness, it immediately follows that P = NP. This intriguing research can be characterized as a constructive theoretical, supported by Monte Carlo simulations, proof of the fundamental equality P = NP. The presented results permit us to develop the most efficient deterministic algorithms for solving numerous practical problems in discrete mathematics, business, management, industry etc. Integer linear programming combinatorics partitions polynomial time algorithms public-key cryptography P =NP Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6400086","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":439913157,"identity":"5adaf892-2473-496a-bfc6-d45497d3c6ba","order_by":0,"name":"Vassilly Voinov","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAApUlEQVRIiWNgGAWjYFACxgYQKQdkNB4gSYsxiEGsFghIBGkkTovB8ea2Bx/bDqevbT/ccIBxz2EitJw52G44s+1w7rYziUCHPSNCi+SMxDZpnjNpudsOgLQcIEFLutn5h0Rq4ZcAaamwSTC7Qawt/DwH2yRnVNgYbrsBtCXhQDphLWzs7c8kPhhIyJudT3/44MMBa8JaUEECqRpGwSgYBaNgFGAHAJATQEM2Df98AAAAAElFTkSuQmCC","orcid":"","institution":"","correspondingAuthor":true,"prefix":"","firstName":"Vassilly","middleName":"","lastName":"Voinov","suffix":""}],"badges":[],"createdAt":"2025-04-08 06:53:33","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6400086/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6400086/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":81344295,"identity":"a2237cfa-223c-42ab-97d4-39f8fe7f942a","added_by":"auto","created_at":"2025-04-25 04:16:53","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":540404,"visible":true,"origin":"","legend":"","description":"","filename":"PartitionsPNPAlgor.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6400086/v1_covered_26f1f329-ce6f-4f2b-9a3f-080c62551bab.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Partitions, the P versus NP problem and applications","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Integer linear programming, combinatorics, partitions, polynomial time algorithms, public-key cryptography, P =NP","lastPublishedDoi":"10.21203/rs.3.rs-6400086/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6400086/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"A new deterministic polynomial-time algorithm for sets of different positive integers partitioning has been introduced. The most important properties of the algorithm are that its time-complexity is O(nlogn) and that it is invariant w.r.t. the number of elements in a particular part. An implementation of this algorithm and the trivial combinatorial show that the classical Partition and the 4-Partition problem, currently considered to be in the NP-complete and the NP-complete in the strong sense complexity classes, respectively, are both solvable in polynomial time, thus belonging to class P. These results permit to introduce the P-complete class of problems reducible to each other by a polynomial transformation. Since it is a subclass of the NP-complete complexity class, from the well-established theory of NP-completeness, it immediately follows that P = NP. This intriguing research can be characterized as a constructive theoretical, supported by Monte Carlo simulations, proof of the fundamental equality P = NP. The presented results permit us to develop the most efficient deterministic algorithms for solving numerous practical problems in discrete mathematics, business, management, industry etc.","manuscriptTitle":"Partitions, the P versus NP problem and applications","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-04-09 05:33:14","doi":"10.21203/rs.3.rs-6400086/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"e85f21dc-f60b-400a-8068-2ee4de1ac7b6","owner":[],"postedDate":"April 9th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-04-25T04:08:41+00:00","versionOfRecord":[],"versionCreatedAt":"2025-04-09 05:33:14","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6400086","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6400086","identity":"rs-6400086","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}