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
    Hartmanis and Stearns' original 1965 framework acknowledg... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

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

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

    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    1 reason against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.Hartmanis-Stearns explicitly defined complexity classes relative to machine models, acknowledging that constants depend on implementation choices.
      ?

      Think about whether this reason is strong or weak

    • 2.Their framework enabled tractability distinctions (P vs NP) that remain useful despite ignoring constants, validating the abstraction's value.
      ?

      Think about whether this reason is strong or weak

    • 3.Asymptotic analysis was presented as a tool for theoretical understanding, not as a complete model of practical runtime behavior.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    1 perspective
    Reason against
    ?
    • 1.The claim overstates acknowledgment: their 1965 paper focused on defining computability classes, not critiquing constant-factor abstraction.
      ?

      Think about whether this reason is strong or weak

    • 2.Modern complexity theory often obscures that polynomial algorithms with large constants can be impractical, misleading practitioners about solvability.
      ?

      Think about whether this reason is strong or weak

    • 3.Ignoring thresholds has real consequences: an O(n³) algorithm with huge constants may outperform O(n log n) only beyond infeasible input sizes.
      ?

      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.

    Key Terms

    knowledge(Distinguished from mere true belief, which may be the product of indoctrination and need not exercise deliberative capacities.)
    Justified true belief — true belief that has been arrived at through the exercise of deliberative capacities, including comparison of and deliberation among alternatives.

    Connections

    2 topics

    Truth & Knowledge1 linkedSkepticism1 linked

    Related

    Asymptotic analysis was presented as a tool for theoretical understanding, not a...Hartmanis-Stearns explicitly defined complexity classes relative to machine mode...Ignoring thresholds has real consequences: an O(n³) algorithm with huge constant...In complexity theory, feasibility is a property of time complexity functions or ...
    +3 moreShow less
    Modern complexity theory often obscures that polynomial algorithms with large co...The claim overstates acknowledgment: their 1965 paper focused on defining comput...

    Details

    Type
    claim
    Perspectives
    2 (1 for, 1 against)
    Edits
    1 edit
    Their framework enabled tractability distinctions (P vs NP) that remain useful d...