OP-10043Computational complexityStatus unassessed
Polynomial-time computability of factoring
Polynomial-time computability of factoring
Formal Conjectures· Specialist source · status unassessed
MSC2020 · 68Qxx
Theory of computing
Theory of computing
39 mapped entries · Browse and filter all →
Counts include all statuses and descendants. Classifications are editorial or inferred from community fields, not an AMS assessment of the problem.
Subcategories
68Q01General topics in the theory of computing068Q04Classical models of computation (Turing machines, etc.)068Q06Networks and circuits as models of computation; circuit complexity068Q07Biologically inspired models of computation (DNA computing, membrane computing, etc.)068Q09Other nonclassical models of computation068Q10Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)068Q11Communication complexity, information complexity068Q12Quantum algorithms and complexity in the theory of computing068Q15Complexity classes (hierarchies, relations among complexity classes, etc.)268Q17Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)368Q19Descriptive complexity and finite models068Q25Analysis of algorithms and problem complexity868Q27Parameterized complexity, tractability and kernelization068Q30Algorithmic information theory (Kolmogorov complexity, etc.)068Q32Computational learning theory068Q42Grammars and rewriting systems068Q45Formal languages and automata068Q55Semantics in the theory of computing068Q60Specification and verification (program logics, model checking, etc.)068Q65Abstract data types; algebraic specification068Q70Algebraic theory of languages and automata068Q80Cellular automata (computational aspects)068Q85Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)068Q87Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)168Q99Theory of computing0
Mapped problems
OP-9980Computational complexityStatus unassessed
Černý Conjecture
Černý Conjecture
Formal Conjectures· Specialist source · status unassessed
OP-9955Computational complexityStatus unassessed
Strong Sensitivity Conjecture (`bs(f) ≤ s(f)^2`)
Strong Sensitivity Conjecture ( bs(f) ≤ s(f)^2 )
Formal Conjectures· Specialist source · status unassessed
OP-9762Computational complexityStatus unassessed
Conjectures in Complexity Theory
Conjectures in Complexity Theory
Formal Conjectures· Specialist source · status unassessed
OP-9469Computational complexityStatus unassessed
PH versus PSPACE
Does the polynomial hierarchy equal the class of languages decidable using polynomial space?
Wikipedia — Computer science· Wikipedia selection · status unassessed
OP-9468Computational complexityStatus unassessed
L versus NL
Can every language decidable in nondeterministic logarithmic space also be decided in deterministic logarithmic space?
Wikipedia — Computer science· Wikipedia selection · status unassessed
OP-9467Computational complexityStatus unassessed
NC versus P
Does every problem decidable in polynomial time admit a uniform family of polynomial-size Boolean circuits of polylogarithmic depth?
Wikipedia — Computer science· Wikipedia selection · status unassessed
OP-6913Computational complexityOpen
Unique Games conjecture
TheoremDB P44 · computational complexity
TheoremDB· Source catalogue assessment
OP-6637Computational complexitySolved
Smallest variable-order OBDD for the middle bit of six-bit multiplication
TheoremDB P2572 · decision diagrams
TheoremDB· Source catalogue assessment
OP-6414Computational complexityStatus unassessed
Polynomial-Factor Hardness for the Closest Vector Problem
TheoremDB P3568 · complexity theory
TheoremDB· Source catalogue assessment
Journals & articles in MSC 68
These are selected sources for the parent class. Article coverage is a first reviewed selection, and may not cover this exact subcategory.
Springer Nature
Discrete geometry and geometric computation
SIAM
Theory of computation
SIAM
Applied and computational mathematics reviews
- The complexity of propositional proofs
2007 · 2 questions extracted
- Randomized numerical linear algebra: Foundations and algorithms
2020 · 0 questions extracted
MSC2020 © Mathematical Reviews (AMS) and zbMATH · CC BY-NC-SA 4.0 · Official PDF, page 176