4 ms·
Hi everyone, I’m an independent researcher and recently completed a formal, self-contained proof that P ≠ NP. The result is based on an explicit language L* ∈
by vicentesteve 1y ago
Hi everyone,
I’m an independent researcher and recently completed a formal, self-contained proof that P ≠ NP. The result is based on an explicit language L* ∈ NP \ P that resists all polynomial-time machines via a certified local test. The core techniques combine locally testable codes, circuit resistance, and diagonalisation.
Unlike many previous attempts, the proof avoids relativization, natural proofs, and algebrization, and relies entirely on constructive combinatorics and meta-complexity arguments. It has been submitted to the Journal of the ACM and also made publicly available here:
ResearchGate (PDF, with DOI): https://doi.org/10.13140/RG.2.2.14071.74408 https://doi.org/10.13140/RG.2.2.14071.74408
I’m sharing this for discussion and feedback from the theoretical CS and cryptography communities. Constructive criticism is welcome — I’d genuinely like to know if any gaps remain. The paper is intended to be rigorous and elementary in its construction.
Thanks in advance, Vicent Esteve Voltes https://orcid.org/0009-0003-1371-7561 https://orcid.org/0009-0003-1371-7561
- LPisGood 1y agoIt seems the PDF and associated DOI have been removed. Is there a reason you haven’t put it on ArXiv?
- akkartik 1y agoI'm able to open the PDF.
- vicentesteve 1y agoThanks for pointing that out. I’m not sure what happened with the DOI — I’m already in contact with ResearchGate to get that fixed. But the PDF is still available and can be viewed or downloaded directly from the ResearchGate page, just below the summary. As for arXiv: I haven't submitted it yet because I need an endorsement and I'm not advanced enough to get one. Because I'm new and haven't written much, I haven't been able to get one yet. I hope I will down the road — I'd really like to submit it there when it's done.
- akkartik 1y agoDid you really (pre)publish these 3 papers in just the last couple of months? https://papers.ssrn.com/sol3/cf_dev/AbsByAuth.cfm?per_id=7560152 https://papers.ssrn.com/sol3/cf_dev/AbsByAuth.cfm?per_id=756...