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
    In complexity theory, feasibility is a property of time c... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Skepticism
    HistoryEditSee Inverse

    In complexity theory, feasibility is a property of time complexity functions or their rates of growth, not of individual natural numbers.

    SkepticismTruth & 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.To apply the Cobham-Edmonds Thesis and judge whether a problem X is feasibly decidable, one considers the order of growth of the time complexity t(n) of the most efficient algorithm for deciding X.
      ?

      Think about whether this reason is strong or weak

    • 2.This analysis applies to functions of type ℕ → ℕ and their rates of growth, not to individual values of n.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Feasibility judgments in practice are always made relative to specific input sizes, not abstract growth functions.
      ?

      Think about whether this reason is strong or weak

    • 2.An algorithm with O(n^2) complexity may be infeasible for n=10^18 yet feasible for n=100, making the individual value decisive.
      ?

      Think about whether this reason is strong or weak

    • 3.Hartmanis and Stearns' original 1965 framework acknowledged that asymptotic analysis abstracts away practically critical constant factors and thresholds.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Gurevich and Shelah's work on feasibility demonstrates that polynomial-time classification fails to track actual computational resource bounds in finite domains.
      ?

      Think about whether this reason is strong or weak

    • 2.If feasibility is purely a property of growth functions, then no fact about any individual natural number can bear on whether a computation is feasible, which is computationally absurd.
      ?

      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

    SkepticismTruth & Knowledge

    Connections

    1 linked claim · 1 topic

    Modality & Possibility1 linked
    In complexity theory, feasibility applies to orders of growth of time complexity...

    Related

    An algorithm with O(n^2) complexity may be infeasible for n=10^18 yet feasible f...Feasibility judgments in practice are always made relative to specific input siz...Gurevich and Shelah's work on feasibility demonstrates that polynomial-time clas...Hartmanis and Stearns' original 1965 framework acknowledged that asymptotic anal...
    +4 moreShow less
    If feasibility is purely a property of growth functions, then no fact about any ...In complexity theory, feasibility applies to orders of growth of time complexity...This analysis applies to functions of type ℕ → ℕ and their rates of growth, not ...

    Similar

    In complexity theory, feasibility applies to orders of growth of time ...97%CET's extension of 'feasible' to all polynomial time functions can div...80%Exponential time complexity is a sufficient condition for classifying ...80%In complexity theory, polynomial (sub-exponential) orders of growth ar...80%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Nonetheless, Parikh showed that for appropriate choices of \(\tau\), any proof of a contradiction in \(\mathsf{PA}^F\) must itself be very long. For instance, if we consider the super-exponential function \(2 \Uparrow 0 = 1\) and \(2 \Uparrow (x+1) = 2^{2 \Uparrow x}\) and let \(\tau\) be the primitive recursive term \(2 \Uparrow 2^k\), it is a consequence of Parikh’s result that any proof of a contradiction in \(\mathsf{PA}^F\) must be on the order of \(2^k\) steps long. e. non-vague) property
    Extraction notes

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

    Details

    To apply the Cobham-Edmonds Thesis and judge whether a problem X is feasibly dec...
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit