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
    Home/Original/inverse
    See Original
    Inverse View

    It is not the case that FACTORIZATION is in coNP

    ?Set your confidence on the premises below to see your aggregate.

    Reasons For

    2 perspectives
    Reason for 1 of 2
    ?
    • 1.The AKS verification of primality operates on the bit-length of each factor, but the product of these lengths can grow super-polynomially relative to the input encoding of n.
      ?

      Think about whether this reason is strong or weak

    • 2.A coNP certificate must be verifiable in polynomial time in the length of the original input ⟨n,m⟩, not in the length of auxiliary components of the certificate.
      ?

      Think about whether this reason is strong or weak

    • 3.Therefore the supporting argument conflates polynomial-time verification of certificate components with polynomial-time verification of the certificate as a whole.
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 2
    ?
    • 1.Uniqueness of prime factorization (the Fundamental Theorem of Arithmetic) guarantees a single valid certificate exists, but does not guarantee that certificate is polynomially sized relative to the binary encoding of n.
      ?

      Think about whether this reason is strong or weak

    • 2.A coNP witness must be both unique-enough to be convincing and polynomially bounded in size; the prime factorization of n can require exponentially many bits relative to log n when n has many small factors.
      ?

      Think about whether this reason is strong or weak

    • 3.Argument 2's appeal to uniqueness addresses soundness of the certificate but is silent on the length constraint that defines membership in coNP.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Membership of ⟨n,m⟩ in the complement of FACTORIZATION can be demonstrated by exhibiting a prime factorization of n in which no factor is less than m
      ?

      Think about whether this reason is strong or weak

    • 2.Prime factorizations are unique, so a single factorization certificate is sufficient
      ?

      Think about whether this reason is strong or weak

    • 3.The primality of individual factors in the factorization can be verified in polynomial time using the AKS algorithm
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Membership of ⟨n,m⟩ in the complement of FACTORIZATION can be certified by exhibiting a prime factorization of n in which no factor is less than m
      ?

      Think about whether this reason is strong or weak

    • 2.The primality of individual factors can be verified in polynomial time by the AKS algorithm
      ?

      Think about whether this reason is strong or weak

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42