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
    Polynomial time computability captures the boundary of fe... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    Polynomial time computability captures the boundary of feasible computability (quasi-inductive argument for CET).

    All sources support itTruth & 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.In cases where a function can be uniformly computed for the class of instances of practical concern, this is typically because a polynomial time algorithm has been discovered that can be implemented on current hardware.
      ?

      Think about whether this reason is strong or weak

    • 2.In cases where a function cannot be uniformly computed for all arguments of practical interest, a polynomial time algorithm has typically not been discovered.
      ?

      Think about whether this reason is strong or weak

    • 3.In many practically intractable cases, there also exists circumstantial evidence that no polynomial time algorithm can exist.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Polynomial time includes algorithms with degree-1000 polynomials that are practically infeasible on any physical hardware within cosmological timescales.
      ?

      Think about whether this reason is strong or weak

    • 2.Sub-polynomial algorithms (e.g., quasi-polynomial) or fixed-parameter tractable algorithms solve many 'intractable' problems for real-world input distributions.
      ?

      Think about whether this reason is strong or weak

    • 3.The quasi-inductive argument conflates mathematical tractability classes with empirical feasibility, committing a category error Hartmanis and Stearns's original complexity theory never intended.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Average-case complexity, not worst-case polynomial time, determines practical feasibility, as Levin's average-case complexity theory and cryptographic practice demonstrate.
      ?

      Think about whether this reason is strong or weak

    • 2.Many NP-complete problems are routinely solved in practice via SAT solvers and heuristics, meaning worst-case intractability fails to track the actual boundary of feasible computation.
      ?

      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

    Truth & KnowledgeAll sources support it

    Connections

    1 topic

    Skepticism1 linked

    Related

    Average-case complexity, not worst-case polynomial time, determines practical fe...In cases where a function can be uniformly computed for the class of instances o...In cases where a function cannot be uniformly computed for all arguments of prac...In many practically intractable cases, there also exists circumstantial evidence...
    +4 moreShow less
    Many NP-complete problems are routinely solved in practice via SAT solvers and h...Polynomial time includes algorithms with degree-1000 polynomials that are practi...Sub-polynomial algorithms (e.g., quasi-polynomial) or fixed-parameter tractable ...The quasi-inductive argument conflates mathematical tractability classes with em...

    Similar

    Practical computability correlates with the existence of polynomial ti...82%A function is feasibly computable if and only if it is computed by som...80%CET classifies as feasible functions computable only by algorithms wit...80%CET counts as feasible any algorithm with time complexity c * n^k rega...79%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Edmonds (1965a) first proposed that polynomial time complexity could be used as a positive criterion of feasibility – or, as he put it, possessing a “good algorithm” – in a paper in which he showed that a problem which might a priori be thought to be solvable only by brute force search (a generalization of \(\sc{PERFECT}\ \sc{MATCHING}\) from above) was decidable by a polynomial time algorithm. Paralleling a similar study of brute force search in the Soviet Union, in a subsequent paper Edmonds
    Extraction notes

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

    Details

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