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
    The polynomial time many-one reducibility relation ≤_P is... — Carmelics
    Home/Modality & Possibility
    HistoryEditSee Inverse

    The polynomial time many-one reducibility relation ≤_P is a preorder (reflexive and transitive).

    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.≤_P is reflexive: every problem is reducible to itself.
      ?

      Think about whether this reason is strong or weak

    • 2.≤_P is transitive: the composition of two polynomial time computable functions is also polynomial time computable, so if X ≤_P Y and Y ≤_P Z then X ≤_P Z.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Polynomial time computability presupposes a fixed machine model, yet Church-Turing thesis variants leave the notion of 'feasible' computation model-relative.
      ?

      Think about whether this reason is strong or weak

    • 2.If the underlying notion of polynomial time is model-relative, then the transitivity proof inherits that relativity, making ≤_P a preorder only relative to a chosen computational substrate, not absolutely.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The identity reduction witnessing reflexivity is trivially well-defined only if problems are individuated extensionally as sets of strings, collapsing intensional distinctions philosophers like Carnap and Frege treat as meaningful.
      ?

      Think about whether this reason is strong or weak

    • 2.If problems are individuated intensionally—by their meaning or cognitive content rather than their extension—then two co-extensional but intensionally distinct problems may not be genuinely self-reducible via a single canonical function, undermining the reflexivity premise.
      ?

      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

    Causation1 linked

    Related

    If problems are individuated intensionally—by their meaning or cognitive content...If the underlying notion of polynomial time is model-relative, then the transiti...Polynomial time computability presupposes a fixed machine model, yet Church-Turi...The identity reduction witnessing reflexivity is trivially well-defined only if ...
    +2 moreShow less
    ≤_P is reflexive: every problem is reducible to itself.≤_P is transitive: the composition of two polynomial time computable functions i...

    Similar

    The polynomial time many-one reducibility relation is a preorder (refl...99%The polynomial-time reducibility relation is transitive.87%NP is closed under polynomial time many-one reducibility, meaning if Y...81%X is polynomial time many-one reducible to Y via function f(x), meanin...80%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    For instance, the following is often described as the single most important open question in all of theoretical computer science: Open Question 1 Is \(\textbf{P}\) properly contained in \(\textbf{NP}\)? 1. 3 Reductions and \(\textbf{NP}\)-completeness Having now introduced some of the major classes studied in complexity theory, we next turn to the question of their internal structure. This can be studied using the notions of the reducibility of one problem to another and of a problem being comp
    Extraction notes

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

    Details

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