|
PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial space can be Polynomial-time reduction, transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formula problem, quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games. Theory A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nondeterministic Constraint Logic
In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. This is a form of reversible logic in that each sequence of edge orientation changes can be undone. Reconfiguration problems for constraint logic, asking for a sequence of moves to connect certain states, connect all states, or reverse a specified edge have been proven to be PSPACE-complete. These hardness results form the basis for proofs that various games and puzzles are PSPACE-hard or PSPACE-complete. Constraint graphs In the simplest version of nondeterministic constraint logic, each edge of an undirected graph has weight either one or two. (The weights may also be represented graphically by drawing edges of weight one as red and edges of weight two as blue.) The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can be solved by Turing machines using ''O''(''f''(''n'')) space for some function ''f'' of the input size ''n'', then we can define PSPACE formally asArora & Barak (2009) p.81 :\mathsf = \bigcup_ \mathsf(n^k). It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,Arora & Barak (2009) p.85 NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a nondeterministic Turing machine without needing much more space (even though it may use much more time).Arora & Barak (2009) p.86 Also, the complements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE PSPACE. Relation among other classes The following re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quantified Boolean Formula Problem
In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic (also known as Second-order propositional logic) where every variable is quantified (or bound), using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false (since there are no free variables). If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT (Quantified SAT). Overview In computational complexity theory, the quantified Boolean formula problem (QBF) is a generalization of the Boolean satisfiability problem in which both existential quantifiers and universal quantifiers can be applied to each variable. Put another way, it asks whether a quantified sentential form over a set of Boolean variables is true or false. For example, the following is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Context-sensitive Grammar
A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any Production (computer science), production rules may be surrounded by a context of terminal symbol, terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by a CSG but not by a context-free grammar. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSGs are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting, although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reconfiguration
In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or Connectivity (graph theory), connectivity of state spaces. Types of problems Here, a state space is a discrete set of configurations of a system or solutions of a combinatorial problem, called states, together with a set of allowed moves linking one state to another. Reconfiguration problems may ask: *For a given class of problems, is the state space always connected? That is, can one transform every pair of states into each other with a sequence of moves? If not, what is the computational complexity of determining whether the state space for a particular problem is connected? *What is the diameter of the state space, the smallest number such that every two states can be transformed into each other with at most moves? *Given two states, what is the complexity of determining whether they can be transformed into each other, or of finding the shortes ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hex (board Game)
Hex (also called Nash) is a two player abstract strategy board game in which players attempt to connect opposite sides of a rhombus-shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash. It is traditionally played on an 11×11 rhombus board, although 13×13 and 19×19 boards are also popular. The board is composed of hexagons called ''cells'' or ''hexes''. Each player is assigned a pair of opposite sides of the board, which they must try to connect by alternately placing a stone of their color onto any empty hex. Once placed, the stones are never moved or removed. A player wins when they successfully connect their sides together through a chain of adjacent stones. Draws are impossible in Hex due to the topology of the game board. Despite the simplicity of its rules, the game has deep strategy and sharp tactics. It also has profound mathematical underpinnings related to the Brouwe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Generalized Game
In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an n\times n board, with 2n pieces on each side. Generalized Sudoku includes Sudokus constructed on an n\times n grid. Complexity theory studies the asymptotic difficulty of problems, so generalizations of games are needed, as games on a fixed size of board are finite problems. For many generalized games which last for a number of moves polynomial in the size of the board, the problem of determining if there is a win for the first player in a given position is PSPACE-complete. Generalized hex and reversi are PSPACE-complete. For many generalized games which may last for a number of moves exponential in the size of the board, the problem of determining if there is a win for the first player in a given position is EXPTIME-complete. Generalized chess, go (with Ja ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reversi
Reversi is a strategy board game for two players, played on an 8×8 uncheckered board. It was invented in 1883. ''Othello'', a variant with a fixed initial setup of the board, was patented in 1971. Basics Two players compete, using 64 identical game pieces ("disks") that are light on one side and dark on the other. Each player chooses one color to use throughout the game. Players take turns placing one disk on an empty square, with their assigned color facing up. After a play is made, any disks of the opponent's color that lie in a straight line bounded by the one just played and another one in the current player's color are turned over. When all playable empty squares are filled, the player with more disks showing in their own color wins the game. History Original version Englishmen Lewis Waterman and John W. Mollett both claim to have invented the game of reversi in 1883, each denouncing the other as a fraud. The game gained considerable popularity in England at the e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Satisfiability Problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisfiability, satisfies a given Boolean logic, Boolean Formula (mathematical logic), formula. In other words, it asks whether the formula's variables can be consistently replaced by the values TRUE or FALSE to make the formula evaluate to TRUE. If this is the case, the formula is called ''satisfiable'', else ''unsatisfiable''. For example, the formula "''a'' AND NOT ''b''" is satisfiable because one can find the values ''a'' = TRUE and ''b'' = FALSE, which make (''a'' AND NOT ''b'') = TRUE. In contrast, "''a'' AND NOT ''a''" is unsatisfiable. SAT is the first problem that was proven to be NP-complete—this is the Cook–Levin theorem. This means that all problems in the complexity class NP (complexity), NP, which includes a wide range of natu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Space Hierarchy Theorem
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...s in space ''n'' log ''n'' than in space ''n''. The somewhat weaker analogous theorems for time are the time hierarchy theorems. The foundation for the hierarchy theorems lies in the intuition that with either more time or more space comes the ability to compute more functions (or decide more languages). The hierarchy theorems are used to demonstrate that the time and space complexity classes form a hierarchy where classes w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second. A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. By contraposition, if no efficient algorithm exists for the first problem, none exists for the second either. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
State Space
In computer science, a state space is a discrete space representing the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the natural numbers starting at 1 and are incremented over time has an infinite discrete state space. The angular position of an undamped pendulum is a continuous (and therefore infinite) state space. Definition State spaces are useful in computer science as a simple model of machines. Formally, a state space can be defined as a tuple [''N'', ''A'', ''S'', ''G''] where: * ''N'' is a Set (mathematics), set of states * ''A'' is a set of arcs connecting the states * ''S'' is a nonempty subset of ''N ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
