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
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    If P equals NP, finding a satisfying valuation for a prop... — Carmelics
    Home/Modality & Possibility
    HistoryEditSee Inverse

    If P equals NP, finding a satisfying valuation for a propositional formula would be no harder than constructing its truth table

    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.Constructing the truth table of a propositional formula is a polynomial-time task
      ?

      Think about whether this reason is strong or weak

    • 2.Finding a satisfying valuation for a propositional formula is an NP problem
      ?

      Think about whether this reason is strong or weak

    • 3.If P equals NP, the difficulty of finding and verifying solutions to all NP problems coincides
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Computational hardness is a property of problem classes under worst-case inputs, not a uniform measure of cognitive or procedural difficulty.
      ?

      Think about whether this reason is strong or weak

    • 2.Constructing a truth table requires explicit enumeration of 2^n rows, while a P=NP SAT algorithm need not enumerate valuations, making 'no harder than' equivocate on distinct complexity notions.
      ?

      Think about whether this reason is strong or weak

    • 3.Aaronson and others in computational complexity theory distinguish between polynomial-time equivalence and step-by-step procedural comparability, which the claim conflates.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The claim presupposes a Platonist reading of complexity classes as describing intrinsic difficulty, whereas constructivists like Bridges and Richman argue complexity is relative to the formal system and proof methods available.
      ?

      Think about whether this reason is strong or weak

    • 2.If P=NP were proven non-constructively, we might establish equivalence without possessing the actual efficient algorithm, leaving the epistemic gap between finding and constructing intact.
      ?

      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

    Aaronson and others in computational complexity theory distinguish between polyn...Computational hardness is a property of problem classes under worst-case inputs,...Constructing a truth table requires explicit enumeration of 2^n rows, while a P=...Constructing the truth table of a propositional formula is a polynomial-time tas...
    +4 moreShow less
    Finding a satisfying valuation for a propositional formula is an NP problemIf P equals NP, the difficulty of finding and verifying solutions to all NP prob...If P=NP were proven non-constructively, we might establish equivalence without p...The claim presupposes a Platonist reading of complexity classes as describing in...

    Similar

    If P = NP, then finding a satisfying valuation for a propositional for...98%If P = NP, then finding a satisfying valuation for a propositional for...92%Finding a satisfying valuation for a propositional formula is an NP pr...90%A formula is in SAT if and only if a satisfying valuation exists84%

    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