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
    A function f(x) is in FP if and only if it is definable b... — Carmelics
    Home/Modality & Possibility
    HistoryEditSee Inverse

    A function f(x) is in FP if and only if it is definable by a Σ^B₁-formula relative to which it is provably total in V¹

    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.The second-order theories V^i characterize the levels of the Polynomial Hierarchy
      ?

      Think about whether this reason is strong or weak

    • 2.Σ^B₁-definability in V¹ captures exactly the polynomial-time computable functions
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Provability in V¹ presupposes a fixed background meta-theory, yet the choice of meta-theory is not itself provably neutral with respect to what counts as 'total'.
      ?

      Think about whether this reason is strong or weak

    • 2.Kreisel's squeezing argument shows that informal notions of computability resist full capture by any single formal provability criterion.
      ?

      Think about whether this reason is strong or weak

    • 3.If the biconditional holds only relative to an assumed consistency of V¹, it cannot serve as a foundational characterization without circularity.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Σ^B₁-definability is a syntactic criterion, but polynomial-time computability is an extensional, machine-relative notion—Benacerraf's identification problem applies here.
      ?

      Think about whether this reason is strong or weak

    • 2.Two functions can be co-extensional over all inputs while differing in their Σ^B₁-definability status under alternative but equally valid formalization choices, undermining the biconditional's necessity claim.
      ?

      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

    Related

    If the biconditional holds only relative to an assumed consistency of V¹, it can...Kreisel's squeezing argument shows that informal notions of computability resist...Provability in V¹ presupposes a fixed background meta-theory, yet the choice of ...The second-order theories V^i characterize the levels of the Polynomial Hierarch...
    +3 moreShow less
    Two functions can be co-extensional over all inputs while differing in their Σ^B...Σ^B₁-definability in V¹ captures exactly the polynomial-time computable function...Σ^B₁-definability is a syntactic criterion, but polynomial-time computability is...

    Similar

    A function f(x) is in FP if and only if it is definable by a Σ^B_1-for...98%A function f(x) is computable in polynomial time if and only if f(x) i...80%A function f(x) is computable in polynomial time if and only if it is ...80%A function f(x) is computable in polynomial time if and only if it is ...78%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    On the other hand, such indirect reference to polynomial rates of growth is avoided in similar functional characterizations of \(\textbf{FP}\) due to Leivant (1994) (using a form of positive second-order definability over strings) and Bellantoni and Cook (1992) (using a structural modification of the traditional primitive recursion scheme). Direct reference to polynomial rates of growth is also avoided in the formulation of the first-order arithmetical theory now known as \(\text{I}\Delta_0\) (w
    Extraction notes

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

    Details

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