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
    A function f(x) is in FP if and only if it is definable b... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Philosophy of Language
    HistoryEditSee Inverse

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

    Philosophy of LanguageTruth & 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 introduced by Zambella (1996) characterize levels of the polynomial hierarchy
      ?

      Think about whether this reason is strong or weak

    • 2.At level i=1, V^1 characterizes FP via Σ^B_1-definability
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Provability in V^1 is a syntactic property, while membership in FP is a semantic/extensional property about computational complexity.
      ?

      Think about whether this reason is strong or weak

    • 2.The identification of syntactic derivability with extensional complexity classes conflates proof-theoretic and model-theoretic notions, a distinction Kreisel's 'unwinding' program treats as non-trivial.
      ?

      Think about whether this reason is strong or weak

    • 3.A function could be provably total in V^1 under one formalization yet fail FP membership under a different but equivalent axiomatization, undermining biconditional stability.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Zambella's characterization presupposes a fixed encoding of finite objects into binary strings, but Cook and Nguyen's 'Logical Foundations of Proof Complexity' (2010) acknowledges that Σ^B_1-definability is encoding-sensitive.
      ?

      Think about whether this reason is strong or weak

    • 2.If the biconditional holds only relative to a privileged encoding scheme, it expresses a representation artifact rather than an intrinsic mathematical equivalence, undermining its status as a foundational characterization.
      ?

      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

    Philosophy of LanguageTruth & Knowledge

    Connections

    1 topic

    Modality & Possibility2 linked

    Related

    A function could be provably total in V^1 under one formalization yet fail FP me...At level i=1, V^1 characterizes FP via Σ^B_1-definabilityIf the biconditional holds only relative to a privileged encoding scheme, it exp...Provability in V^1 is a syntactic property, while membership in FP is a semantic...
    +3 moreShow less
    The identification of syntactic derivability with extensional complexity classes...The second-order theories V^i introduced by Zambella (1996) characterize levels ...Zambella's characterization presupposes a fixed encoding of finite objects into ...

    Similar

    A function f(x) is in FP if and only if it is definable by a Σ^B₁-form...98%A function f(x) is computable in polynomial time if and only if f(x) i...81%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 ...80%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    We define the class \(\mathcal{F}\) of functions definable by limited recursion on notation to be the least class containing \(\mathcal{F}_0\) and closed under composition and the foregoing scheme. 4 (Cobham 1965; Rose 1984) \(f(\vec{x}) \in \textbf{FP}\) if and only if \(f(\vec{x}) \in \mathcal{F}\). 4 is significant because it provides another machine-independent characterization of an important complexity class. Recall, however, that Cobham was working at a time when the mathematical status
    Extraction notes

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

    Details

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