Not signed in

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

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex 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 foundation 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 homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab 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 stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorCorbin
   • CommentTimeOct 16th 2021
   • PermaLink
   Author: Corbin
   Format: MarkdownItexStub. 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. <a href="https://ncatlab.org/nlab/revision/complexity+class/1">v1</a>, <a href="https://ncatlab.org/nlab/show/complexity+class">current</a>

   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

2. • CommentRowNumber2.
   • CommentAuthorUrs
   • CommentTimeOct 17th 2021
   • PermaLink
   Author: Urs
   Format: MarkdownItexThe 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.

   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.

3. • CommentRowNumber3.
   • CommentAuthorCorbin
   • CommentTimeOct 17th 2021
   • PermaLink
   Author: Corbin
   Format: MarkdownItexRewrote 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. <a href="https://ncatlab.org/nlab/revision/diff/complexity+class/2">diff</a>, <a href="https://ncatlab.org/nlab/revision/complexity+class/2">v2</a>, <a href="https://ncatlab.org/nlab/show/complexity+class">current</a>

   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