HackerPapers

arXiv:1604.03758cs.CC

The Existence of the Tau One-Way Functions Class as a Proof that P != NP

Javier A. Arroyo-Figueroa

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
Corrected title and an error at the end of Section 7
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.CRCryptography and Security

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Apr 2016 to Apr 2016. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.