For Publishers
DiscoveryMetadataPeer reviewHostingPublishing
For Researchers
JoinPublishReviewCollect
Register
Blog
About
Search
Advanced search
My ScienceOpen
Search
For Publishers
For Researchers
Blog
About
245
views
1
references
 Top references
cited by
0
    
0 reviews
 Review
1
comments
 Comment
0
recommends
+1 Recommend
1 collections
    0
    shares
      272
      similar
       All similar

      One-Click Submission System Now Available for SO Preprints, learn more on how this works in our blog post and don't forget to check the video, too!

      scite_
      0
      0
      0
      0
      Smart Citations
      0
      0
      0
      0
      Citing PublicationsSupportingMentioningContrasting
      View Citations

      See how this article has been cited at scite.ai

      scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

      Version and Review History
      Preprint version 3
      2
      Preprint version 2
      Reviewed by Jorge Félix Martínez PazosReviewed by Sergi Simon
      2
      Preprint version 1
      Reviewed by Jorge Félix Martínez PazosReviewed by Sergi Simon
       
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Note for the P versus NP Problem

      Preprint
      In review
      research-article
      Author(s):   1 ,
      Publication date (Electronic preprint):
      Journal: ScienceOpen Preprints
      Publisher: ScienceOpen
      Keywords: Complexity classes, boolean formula, graph, completeness, polynomial time
      Bookmark

            Revision notes

            Sergi Simon detected an error in a single sentence related to the definition of the K-CLOSURE problem. We think this current version is good enough this time.

            Abstract

            Content

            Author and article information

            Journal
            Title: ScienceOpen Preprints
            Publisher: ScienceOpen
            Publication date (Electronic preprint): 20 April 2024
            Affiliations
            [1 ] GROUPS PLUS TOURS INC., 9611 Fontainebleau Blvd, Miami, FL, 33172, USA;
            Author notes
            Author information
            https://orcid.org/0000-0001-8210-4126
            Article
            DOI: 10.14293/PR2199.000759.v3
            SO-VID: d6a6122f-1ee6-4421-854c-7ac36cacb691
            License:

            This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

            History
            Date received : 15 March 2024
            Categories

            Data availability: Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
            ScienceOpen disciplines: Data structures & Algorithms,Theoretical computer science
            Keywords: boolean formula,completeness,graph,polynomial time,Complexity classes

            References

            1. Fortnow Lance. The status of the P versus NP problem. Communications of the ACM. Vol. 52(9):78–86. 2009. Association for Computing Machinery (ACM). [Cross Ref]

            Comments

            wrote:

            Re-commenting on the latest version:

            Sorry to burst your bubble, but the book you cite is incorrect. Notice that the only source for the claim that K-CLOSURE is NP-complete is a never published private communication. In fact, if K-CLOSURE was actually NP-complete, there would be a much shorter proof that P = NP; just take the empty set of vertices as a solution! If the problem is instead about a non-empty subset of vertices (which the statement doesn't clarify), then it is the same problem as finding the smallest weakly connected component of the directed graph, which would also be a shorter proof.

             

            Amazingly, your thought process seems to be correct, although very informally written. I would recommend reading other math papers and consulting peers to get the right tone. Keep at it!

            2025-03-27 14:54 UTC
            +1

            Comment on this article