|
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] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
