๐ฎ
๐ฎ
The Ethereal
The Existence of the Tau One-Way Functions Class as a Proof that P != NP
April 12, 2016 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Javier A. Arroyo-Figueroa
arXiv ID
1604.03758
Category
cs.CC: Computational Complexity
Cross-listed
cs.CR
Citations
0
Venue
arXiv.org
Last Checked
3 months ago
Abstract
We prove that P != NP by proving the existence of a class of functions we call Tau, each of whose members satisfies the conditions of one-way functions. Each member of Tau is a function computable in polynomial time, with negligible probability of finding its inverse by any polynomial probabilistic algorithm. We also prove that no polynomial-time algorithm exists to compute the inverse of members of Tau, and that the problem of computing the inverse of Tau cannot be reduced to FSAT in polynomial time.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal