Skip to content
Carmelics
TopicsThinkersChangesContributorsLoading account…

    Carmelics

    A reasoning platform. Break down any belief into clear reasons, explore both sides, and weigh the evidence honestly.

    Navigate

    • Topics
    • Search
    • Recent Changes
    • Contribute
    • How It Works
    • Glossary
    • Thinkers
    • Contributors
    • About
    • Statistics
    • Terms
    • Privacy

    Database

    Statements
    —
    Perspectives
    —
    Topics
    —

    Press ? for keyboard shortcuts

    LoyalLoyalJusticeJustice
    Made withinDC&Austin
    If P equals NP, factoring a natural number would be no mo... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    If P equals NP, factoring a natural number would be no more difficult than verifying that a given factorization is correct

    Modality & PossibilityTruth & Knowledge
    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    2 reasons against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.Verifying a factorization is a polynomial-time task
      ?

      Think about whether this reason is strong or weak

    • 2.Integer factorization is not known to be in P but is in NP
      ?

      Think about whether this reason is strong or weak

    • 3.If P equals NP, finding and verifying solutions to NP problems are equally difficult
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.P=NP would equalize worst-case complexity classes, but factoring's average-case hardness could persist independently of class membership.
      ?

      Think about whether this reason is strong or weak

    • 2.Levin's average-case complexity theory shows that worst-case class collapse does not entail uniform tractability across problem instances.
      ?

      Think about whether this reason is strong or weak

    • 3.The claim conflates decision-problem complexity with the search problem of producing a factorization, which require separate complexity-theoretic treatment.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Integer factorization is not NP-complete, so P=NP need not imply factoring is in P unless factoring reduces to an NP-complete problem.
      ?

      Think about whether this reason is strong or weak

    • 2.Factoring occupies an intermediate status under standard conjectures, placing it in a region where P=NP may not collapse its complexity to P.
      ?

      Think about whether this reason is strong or weak

    Sign in or register to share your perspective on this statement.

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Topics

    Modality & PossibilityTruth & Knowledge

    Connections

    1 topic

    Proof of definition segments2 linked

    Related

    Factoring occupies an intermediate status under standard conjectures, placing it...If P equals NP, finding and verifying solutions to NP problems are equally diffi...Integer factorization is not NP-complete, so P=NP need not imply factoring is in...Integer factorization is not known to be in P but is in NP
    +4 moreShow less
    Levin's average-case complexity theory shows that worst-case class collapse does...P=NP would equalize worst-case complexity classes, but factoring's average-case ...The claim conflates decision-problem complexity with the search problem of produ...Verifying a factorization is a polynomial-time task

    Similar

    If P = NP, then finding a satisfying valuation for a propositional for...85%Integer factorization is not known to be in P but is in NP80%If P equals NP, then finding a solution to any NP problem would be no ...79%If P equals NP, finding and verifying solutions to NP problems are equ...77%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    It is thus also reasonable to ask how we might modify the definition of \(\mathfrak{N}\) so as to obtain a characterization of probabilistic algorithms which we might usefully employ. [33] This class can be most readily defined relative to a model of computation known as the probabilistic Turing machine \(\mathfrak{C}\). Such a device \(C\) has access to a random number generator which produces a new bit at each step in its computation but is otherwise like a conventional Turing machine. The act
    Extraction notes

    Validity: Extracted via Max plan + API grounding/validity checks

    Details

    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit