Not signed in (Sign In)

Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-theory cohesive-homotopy-type-theory cohomology colimits combinatorics complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homology homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory kan lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology natural nforum nlab nonassociative noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topological topology topos topos-theory type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorCorbin
    • CommentTimeOct 16th 2021

    Stub. I don’t like this approach but I’m not sure how to make it better.

    I tried to give a type-theoretic approach to avoid the classic problem where we overspecialize on Turing machines, but I’m not great with type theory.

    v1, current

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeOct 17th 2021

    The first sentence currently

    In computational complexity theory, many problems have similar behavior, leading to similar algorithms for solving families of problems.

    doesn’t make the intended logical sense. It’s not that problems in complexity theory have similar behaviour, but that in computer science there are classes of computational problems of similar complexity, and complexity theory is the art of grouping these together. The classification of problems in complexity theory would lead to some meta-complexity theory, instead.

    The second sentence seems unnecessary at this point, or other wise it could benefit from starting with “For example, …”

    Then the third sentence

    A complexity class is a collection of problems which all can be executed on a single type of computer with similar resource usage.

    should probably rather read: “A complexity class is a collection of computational problems which, when executed on a given computer, have similar resource usage.

    You claim in #1 to give a “type theoretic approach” but the only occurrence of the word “type theory” currently is as a synonym for “model of computation”. Since you say you don’t feel in command of what you are saying about type theory anyway, you might just omit saying it, the entry text wouldn’t seem to lose anything at this point.

    • CommentRowNumber3.
    • CommentAuthorCorbin
    • CommentTimeOct 17th 2021

    Rewrote opening paragraph, and added a second paragraph to generalize appropriately. As long as I’m here, add an example supporting the second paragraph.

    Removed mention of type theory. Sorry, lately I haven’t been able to tell the difference between type theories and programming languages.

    diff, v2, current

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)