Data Structures and Algorithms

2308 Submissions

[3] viXra:2308.0141 [pdf] submitted on 2023-08-21 22:19:56

On a Solution of "P vs NP" Millennium Prize Problem Based on the Subset Sum Problem

Authors: B. Sinchev, A. B. Sinchev, A. М. Mukhanova
Comments: 7 Pages.

Given a set of distinct non-negative integers X^n and a target certificate S parametrized in: ∃X^k⊆X^n,∑_(x_i∈X^k)[]x_i =S (k=|X^k |,n=|X^n |). We present a polynomial solution of the subset sum problem with time complexity T≤O(n^2) and space complexity S≤O(n^2 ), so that P = NP.
Category: Data Structures and Algorithms

[2] viXra:2308.0047 [pdf] submitted on 2023-08-09 22:25:25

A New Simple Constructive Proof of Kannan’s Theorem

Authors: Sunny Daniels
Comments: 4 Pages. "Complexity Theory" would almost certainly be the best arXiv category for this paper, but there doesn't seem to be any corresponding viXra category.

I appreciate the feedback from Fortnow (the author of [1]) on my recent viXra article [2], and inparticular him supplying me with a definition of the standard polynomial-time universal Turingmachine[4]. In [3], I clarified the way in which my construction and proofs in [2] could be re-worked to be analogous to the more usual definition of a universal Sigma_2^P Turing machine.Shortly after publishing [2], I realised that my construction in [2] or [3] gives rise to a very, verysimple new constructive proof of Kannan’s theorem: much simpler than anything that has beenpublished before, if I am not mistaken, and even simpler than my proposed "layer by layer" proof in[2]. I suspect that Fornow realised this soon after reading [2]: his e-mail correspondence with meseems to hint at this. If so, I appreciate him giving me the opportunity to pubish this new proofmyself!I present a sketch of this new proof here.
Category: Data Structures and Algorithms

[1] viXra:2308.0031 [pdf] submitted on 2023-08-06 18:46:31

My New Constructive Kannan’s Theorem Construction Using More Standard Conventions

Authors: Sunny Daniels
Comments: 6 Pages. "Complexity Theory" would almost certainly be the best arXiv category for this paper, but there doesn't seem to be any corresponding viXra category.

I appreciate the feedback from Fortnow (the author of [1]) on my recent viXra article [2], and inparticular him supplying me with a definition of the standard polynomial-time universal Turingmachine. In this article I re-work my previous definitions and proofs to put in the circuit sizeexponent "k" explicitly (rather than the pseudo-variable "99" in [2]) and use more standardconventions for the derivation of my construction from the standard polynomial-time universalTuring machine construction.
Category: Data Structures and Algorithms