|
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 * |
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 (polynomial space) and if every other problem that can be solved in polynomial space can be 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 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 of memory (it belongs to PSPACE) and every problem in PSPACE can be tr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Node Kayles
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, or edges meet. *Node (autonomous system), behaviour for an ordinary differential equation near a critical point *Singular point of an algebraic variety, a type of singular point of a curve In science and engineering Astronomy *Orbital node, the points where an orbit crosses a plane of reference ** Lunar node, where the orbits of the sun and moon intersect ** Longitude of the ascending node, how orbital nodes are parameterized Biology *Lymph node, an immune system organ used to store white blood cells *Node of Ranvier, periodic gaps in the insulating myelin sheaths of myelinated axons *Sinoatrial node and atrioventricular node, specialized tissues in the heart responsible for initiating and coordinating the heartbeat *Primitive knot or pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Acyclic Directed Graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling). Directed acyclic graphs are sometimes instead called acyclic directed graphs or acyclic digraphs. Definitions A graph is formed by vertices and by edges connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a directed graph, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Toniann Pitassi
Toniann Pitassi is a Canadian and American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto. Academic career A native of Pittsburgh, Pitassi earned bachelor's and master's degrees at Pennsylvania State University before moving to the University of Toronto for her doctoral studies; she earned her Ph.D. in 1992 from Toronto under the supervision of Stephen Cook. After postdoctoral studies at the University of California, San Diego and faculty positions at the University of Pittsburgh and University of Arizona, she returned to Toronto in 2001, and was a professor in the University of Toronto Department of Computer Science and University of Toronto Department of Mathematics until 2021, when she joined the faculty of Columbia University. She was an invited speaker at International Congress of Ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pebble Game
In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed graph, directed acyclic graph according to certain rules: * A given step of the game consists of either placing a pebble on an empty vertex or removing a pebble from a previously pebbled vertex. * A vertex may be pebbled only if all its predecessors have pebbles. * The objective of the game is to successively pebble each vertex of ''G'' (in any order) while minimizing the number of pebbles that are ever on the graph simultaneously. Running time The trivial solution is to pebble an ''n''-vertex graph in ''n'' steps using ''n'' pebbles. Hopcroft, Paul and Valiant showed that any vertex of an ''n''-vertex graph can be pebbled with O(''n''/log ''n'') pebbles where the constant depends on the maximum in-degree. This enabled them to prove that DTIME(''f''(''n'')) is contained in DSPACE(''f''(''n'')/log ''f''(''n'')) for all time-constructible fun ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Super Mario Bros
is a platform game developed and published by Nintendo for the Nintendo Entertainment System (NES). The successor to the 1983 arcade game ''Mario Bros.'' and the first game in the ''Super Mario'' series, it was first released in 1985 for the Famicom in Japan. Following a limited US release for the NES, it was ported to international arcade game, arcades for the Nintendo Vs. System, Nintendo VS. System in early 1986. The NES version received a wide release in North America that year and in PAL regions in 1987. Players control Mario, or his brother Luigi in the multiplayer mode, as they traverse the Mushroom Kingdom to rescue Princess Toadstool from King Koopa (later named Bowser (character), Bowser). They traverse side-scrolling video game, side-scrolling stages while avoiding hazards such as enemies and pits with the aid of power-ups such as the Super Mushroom, Fire Flower, and Starman. The game was designed by Shigeru Miyamoto and Takashi Tezuka as "a grand culmination" of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sokoban
is a puzzle video game in which the player pushes boxes around in a warehouse, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982. Gameplay The game is played on a board of squares, where each square is a floor or a wall. Some floor squares contain boxes, and some floor squares are marked as storage locations. The player is confined to the board and may move horizontally or vertically onto empty squares (never through walls or boxes). The player can move a box by walking up to it and push it to the square beyond. Boxes cannot be pulled, and they cannot be pushed to squares with walls or other boxes. The number of boxes equals the number of storage locations. The puzzle is solved when all boxes are placed at storage locations. Selected official releases Development ''Sokoban'' was created in 1981 by Hiroyuki Imabayashi. The first commercial game was published in December 1982 by Thinking Rabbit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Computing
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ''SIAM J. Comput.'', its publisher and contributors frequently use the shorter abbreviation ''SICOMP''. SICOMP typically hosts the special issues of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) and the Annual ACM Symposium on Theory of Computing (STOC), where about 15% of papers published in FOCS and STOC each year are invited to these special issues. For example, Volume 48 contains 11 out of 85 papers published in FOCS 2016. References * External linksSIAM Journal on Computing on |
Peter Shor
Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics at MIT. He is known for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer. Early life and education Shor was born in New York City to Joan Bopp Shor and S. W. Williston Shor, of Jewish descent. He grew up in Washington, D.C. and Mill Valley, California. While attending Tamalpais High School, he placed third in the 1977 USA Mathematical Olympiad. After graduation that year, he won a silver medal at the International Math Olympiad in Yugoslavia (the U.S. team achieved the most points per country that year). He received his B.S. in Mathematics in 1981 for undergraduate work at Caltech, and was a Putnam Fellow in 1978. He earned his PhD in Applied Mathematics from MIT in 1985. His doctoral advisor was F. Thomson Leighton, and his thesi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Anne Condon
Anne Elizabeth Condon, is an Irish-Canadian computer scientist, professor, and former head of the Computer Science Department of the University of British Columbia. Her research focuses on computational complexity theory, DNA computing, and bioinformatics.Faculty web page University of British Columbia, retrieved 2011-11-20.Who We Are: Anne Condon , Anita Borg Institute for Women and Technology, retrieved 2011-11-20. She has also held the /General Motors Canada Chair for Women in Science and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mahjong Solitaire
Mahjong solitaire (also known as Shanghai solitaire, electronic or computerized mahjong, solitaire mahjong or simply mahjong) is a single-player matching game that uses a set of mahjong tiles rather than cards. It is more commonly played on a computer than as a physical tabletop game. Its name comes from the four-player game mahjong, but it is played entirely differently. Play The 144 tiles are arranged in a four-layer pattern with their faces upwards. A tile is said to be open or exposed if it can be moved either left or right without disturbing other tiles. The goal is to match open pairs of identical tiles and remove them from the board, exposing the tiles under them for play. The game is won when all pairs of tiles have been removed from the board, and lost if the remaining tiles contain no exposed pairs. Mathematical analysis Playing Mahjong solitaire optimally in the sense to maximize the probability of removing all tiles is PSPACE-complete, and the game is NP-comple ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rush Hour (board Game)
''Rush Hour'' is a sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. It is now being manufactured by ThinkFun (formerly Binary Arts). ThinkFun now sells ''Rush Hour'' spin-offs ''Rush Hour Jr.'', ''Safari Rush Hour'', ''Railroad Rush Hour'', ''Rush Hour Brain Fitness'' and ''Rush Hour Shift'', with puzzles by Scott Kim. Game The board is a 6×6 grid with grooves in the tiles to allow cars to slide, card tray to hold the cards, current active card holder and an exit hole. The game comes with 16 vehicles (12 cars, 4 trucks), each colored differently, and 40 puzzle cards. Cars and trucks are both one square wide, but cars are two squares long and trucks are three squares long. Vehicles can only be moved along a straight line on the grid; rotation is forbidden. Puzzle cards, each with a level number that indicates the difficulty of the challenge, show the starting positions of cars and trucks. Not all cars and trucks are us ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
