|
Lists Of Problems
The following articles contain lists of problems: *List of undecidable problems *Lists of unsolved problems *List of NP-complete problems *List of PSPACE-complete problems Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: * Amazons * Atomix * Checkers * Dyson Telesc ... {{DEFAULTSORT:Problems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of Undecidable Problems
In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. More formally, an undecidable problem is a problem whose language is not a recursive set; see the article Decidable language. There are uncountably many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of Turing recognizable languages: i.e., such undecidable languages may be recursively enumerable. Many, if not most, undecidable problems in mathematics can be posed as word problems: determining when two distinct strings of symbols (encoding some mathematical concept or object) represent the same object or not. For undecidability in axiomatic mathematics, see List of stateme ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lists Of Unsolved Problems
List of unsolved problems may refer to several notable conjectures or open problems in various academic fields: Natural sciences, engineering and medicine * Unsolved problems in astronomy * Unsolved problems in biology * Unsolved problems in chemistry * Unsolved problems in engineering * Unsolved problems in geoscience * Unsolved problems in medicine * Unsolved problems in neuroscience * Unsolved problems in physics Mathematics, philosophy and information sciences * Unsolved problems in mathematics * Unsolved problems in statistics * Unsolved problems in computer science * Unsolved problems in philosophy * Unsolved problems in information theory Social sciences and languages * Unsolved problems in economics * Unsolved problems in fair division * Unsolved problems in linguistics See also * Cold case (unsolved crimes) * List of ciphertexts * List of NP-complete problems * List of PSPACE-complete problems * List of paradoxes * List of undecidable problems * List of unsolve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of NP-complete Problems
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . Graphs and hypergraphs Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. Facebook or LinkedIn). * 1-planarity *3-dimensional matching * Bandwidth problem *Bipartite dimension * Capacitated minimum spanning tree *Route inspection problem (also called Chinese postman problem) for mixed graphs (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem. * Clique cover problem *Clique problem *Complete coloring, a.k.a. achromatic number *Cycle rank a.k.a. Rank coloring * Degree-constrained s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of PSPACE-complete Problems
Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: * Amazons * Atomix * Checkers * Dyson Telescope Game * Cross Purposes * Geography * Two-player game version of Instant Insanity * Ko-free Go * Ladder capturing in GoGo ladders are PSPACE-complete * * Hex * Konane * |