text:
P-complete

In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.

The notion of P-complete decision problems is useful in the analysis of:

 * which problems are difficult to parallelize effectively,
 * which problems are difficult to solve in limited space.

specifically when stronger notions of reducibility than polytime-reducibility are considered.

The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stronger than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the stronger log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller.

Motivation
The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine. It is not known whether NC = P. In other words, it is not known whether there are any tractable problems that are inherently sequential. Just as it is widely suspected that P does not equal NP, so it is widely suspected that NC does not equal P.

Similarly, the class L contains all problems that can be solved by a sequential computer in logarithmic space. Such machines run in polynomial time because they can have a polynomial number of configurations. It is suspected that L ≠ P; that is, that some problems that can be solved in polynomial time also require more than logarithmic space.

Similarly to the use of NP-complete problems to analyze the P = NP question, the P-complete problems, viewed as the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the NC = P question. Finding an efficient way to parallelize the solution to some P-complete problem would show that NC = P. It can also be thought of as the "problems requiring superlogarithmic space"; a log-space solution to a P-complete problem (using the definition based on log-space reductions) would imply L = P.

The logic behind this is analogous to the logic that a polynomial-time solution to an NP-complete problem would prove P = NP: if we have a NC reduction from any problem in P to a problem A, and an NC solution for A, then NC = P. Similarly, if we have a log-space reduction from any problem in P to a problem A, and a log-space solution for A, then L = P.

P-complete problems
The most basic P-complete problem under logspace many-one reductions is following: given a Turing machine $$M$$, an input for that machine x, and a number T (written in unary), $$\langle M,x,T \rangle$$ does that machine halt on that input within the first T steps? For any x in $$L$$ in P, output the encoding of the Turing machine which accepts it in polynomial-time, the encoding of x itself, and a number of steps $$T=p(|x|)$$ corresponding to the p which is there polynomial-time bound on the operation of the Turing Machine $$M_L$$ deciding $$L$$, $$\langle M,x,p(|x|) \rangle$$. The machine M halts on x within $$p(|x|)$$ steps if and only if x is in L. Clearly, if we can parallelize a general simulation of a sequential computer (ie. The Turing machine simulation of a Turing machine), then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so is every other problem in P. If the number of steps is written in binary, the problem is EXPTIME-complete. This problem illustrates a common trick in the theory of P-completeness. We aren't really interested in whether a problem can be solved quickly on a parallel machine. We're just interested in whether a parallel machine solves it much more quickly than a sequential machine. Therefore, we have to reword the problem so that the sequential version is in P. That is why this problem required T to be written in unary. If a number T is written as a binary number (a string of n ones and zeros, where n = log T), then the obvious sequential algorithm can take time 2n. On the other hand, if T is written as a unary number (a string of n ones, where n = T), then it only takes time n. By writing T in unary rather than binary, we have reduced the obvious sequential algorithm from exponential time to linear time. That puts the sequential problem in P. Then, it will be in NC if and only if it is parallelizable.

Many other problems have been proved to be P-complete, and therefore are widely believed to be inherently sequential. These include the following problems which are P-complete under at least logspace reductions, either as given, or in a decision-problem form:
 * Circuit Value Problem (CVP) – Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate.
 * Restricted Case of CVP – Like CVP, except each gate has two inputs and two outputs (F and Not F), every other layer is just AND gates, the rest are OR gates (or, equivalently, all gates are NAND gates, or all gates are NOR gates), the inputs of a gate come from the immediately preceding layer
 * Linear programming – Maximize a linear function subject to linear inequality constraints
 * Lexicographically First Depth First Search Ordering – Given a graph with fixed ordered adjacency lists, and nodes u and v, is vertex u visited before vertex v in a depth-first search induced by the order of the adjacency lists?
 * Context Free Grammar Membership – Given a context-free grammar and a string, can that string be generated by that grammar?
 * Horn-satisfiability – given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the boolean satisfiability problem.
 * Game of Life – Given an initial configuration of Conway's Game of Life, a particular cell, and a time T (in unary), is that cell alive after T steps?
 * LZW (algorithm) (1978 paradigm) Data Compression – given strings s and t, will compressing s with an LZ78 method add t to the dictionary? (Note that for LZ77 compression such as gzip, this is much easier, as the problem reduces to "Is t in s?".)
 * Type inference for partial types – Given an untyped term from the lambda calculus, determine whether this term has a partial type.

Most of the languages above are P-complete under even stronger notions of reduction, such as uniform $$AC^0$$ many-one reductions, DLOGTIME reductions, or polylogarithmic projections.

In order to prove that a given problem in P is P-complete, one typically tries to reduce a known P-complete problem to the given one.

In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse language that is P-complete, then L = P.

P-complete problems may be solvable with different time complexities. For instance, the Circuit Value Problem can be solved in linear time by a topological sort. Of course, because the reductions to a P-complete problem may have different time complexities, this fact does not imply that all the problems in P can also be solved in linear time.

title: P-complete


text:
96 BC

Year 96 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Ahenobarbus and Longinus (or, less frequently, year 658 Ab urbe condita). The denomination 96 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * Consuls: Gaius Cassius Longinus and Gnaeus Domitius Ahenobarbus
 * Cyrene is left to the people of the Roman Republic by its ruler Ptolemy Apion.

Greece

 * Seleucus VI Epiphanes becomes king of the Seleucid Empire following the death of his father Antiochus VIII Grypus, and defeating in battle Antiochus IX Cyzicenus.

Asia

 * Start of the Taishi era in the Han dynasty.

Births

 * Galeria Copiola, Roman dancer d. 9 AD

Deaths

 * Antiochus VIII Grypus, king of the Seleucid Empire
 * Antiochus IX Cyzicenus, king of the Seleucid Empire
 * Gongsun Ao, Chinese general of the Han dynasty
 * Ptolemy Apion, king of Cyrenaica (modern Libya)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: 96 BC


text:
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 transformed in polynomial time into an equivalent instance of the given problem.

The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes P (polynomial time) and NP (non-deterministic polynomial time), but that is not known. It is known that they lie outside of the class NC, a class of problems with highly efficient parallel algorithms, because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.

The transformations that are usually considered in defining PSPACE-completeness are polynomial-time many-one reductions, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using Turing reductions, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems. Other types of reductions, such as many-one reductions that always increase the length of the transformed input, have also been considered.

A version of the Berman–Hartmanis conjecture for PSPACE-complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial-time bijections.

Formal languages
Given a regular expression $$R$$, determining whether it generates every string over its alphabet is PSPACE-complete.

The first known PSPACE-complete problem was the word problem for deterministic context-sensitive grammars. In the word problem for context-sensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations. The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and showed that every (possibly non-deterministic) program computable in linear space could be converted into the parsing of a context-sensitive grammar, in a way which preserves determinism. In 1970, Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE.

Logic
A standard PSPACE-complete problem, used in many other PSPACE-completeness results, is the quantified Boolean formula problem, a generalization of the Boolean satisfiability problem. The quantified Boolean formula problem takes as input a Boolean expression, with all of its variables quantified either universally or existentially, for example: $$\exists x_1 \, \forall x_2 \, \exists x_3 \, \forall x_4: (x_1 \lor \neg x_3 \lor x_4) \land (\neg x_2 \lor x_3 \lor \neg x_4).$$ The output of the problem is the value of the quantified expression. Finding this value is PSPACE-complete.

Reconfiguration
Reconfiguration problems concern the connectivity of a state space of solutions to a combinatorial problem. For instance, testing whether two 4-colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4-coloring, is PSPACE-complete, even though the same problem for 3-colorings can be solved in polynomial time. Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE-completeness proofs of many other problems in this area, involve nondeterministic constraint logic, in which the states are orientations of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge.

Puzzles and games
The quantified Boolean formula problem can be interpreted as a game by two players, a verifier and a falsifier. The players make moves that fill in values for the quantified variables, in the order they are nested, with the verifier filling in existentially quantified variables and the falsifier filling in universally quantified variables; the game is won by the verifier if the filled-in formula becomes true, and by the falsifier otherwise. A quantified formula is true if and only if the verifier has a winning strategy. Similarly, the problem of determining the winner or loser of many other combinatorial games turns out to be PSPACE-complete. Examples of games that are PSPACE-complete (when generalized so that they can be played on an $$n\times n$$ board) are the games Hex and Reversi. Some other generalized games, such as chess, checkers (draughts), and Go are EXPTIME-complete because a game between two perfect players can be very long, so they are unlikely to be in PSPACE. But they will become PSPACE-complete if a polynomial bound on the number of moves is enforced.

It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems, and include the solitaire games Rush Hour, Mahjong, Atomix and Sokoban, and the mechanical computer Turing Tumble.

PSPACE-completeness is based on complexity as a function of the input size $$n$$, in the limit as $$n$$ grows without bound. Puzzles or games with a bounded number of positions such as chess on a conventional $$8\times 8$$ board cannot be PSPACE-complete, because they could be solved in constant time and space using a very large lookup table. To formulate PSPACE-complete versions of these games, they must be modified in a way that makes their number of positions unbounded, such as by playing them on an $$n\times n$$ board instead. In some cases, such as for chess, these extensions are artificial.

title: PSPACE-complete


text:
NP-easy

In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP.

In other words, a problem X is NP-easy if and only if there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y. This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle).

NP-easy is another name for FPNP (see the function problem article) or for FΔ2P (see the polynomial hierarchy article).

An example of an NP-easy problem is the problem of sorting a list of strings. The decision problem "is string A greater than string B" is in NP. There are algorithms such as quicksort that can sort the list using only a polynomial number of calls to the comparison routine, plus a polynomial amount of additional work. Therefore, sorting is NP-easy.

There are also more difficult problems that are NP-easy. See NP-equivalent for an example.

The definition of NP-easy uses a Turing reduction rather than a many-one reduction because the answers to problem Y are only TRUE or FALSE, but the answers to problem X can be more general. Therefore, there is no general way to translate an instance of X to an instance of Y with the same answer.

title: NP-easy


text:
Talk:Mountain biking/Archive 1

Why was this page moved from "Mountainbiking"? I guess "Mountain bicycling" would be the proper term, but I have NEVER heard anybody using it. Google does give a number of hits, but Mountainbiking/mountain biking has far mor than mountain bicycling. So why the change? jheijmans

I agree and would go for Mountain biking. user:Elliot100

title: Talk:Mountain biking/Archive 1


text:
NP-equivalent

In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems.

For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integers, FIND-SUBSET-SUM is the problem of finding some nonempty subset of the integers that adds up to zero (or returning the empty set if there is no such subset). This optimization problem is similar to the decision problem SUBSET-SUM. Given a set of integers, SUBSET-SUM is the problem of finding whether there exists a subset summing to zero. SUBSET-SUM is NP-complete.

To show that FIND-SUBSET-SUM is NP-equivalent, we must show that it is both NP-hard and NP-easy.

Clearly it is NP-hard. If we had a black box that solved FIND-SUBSET-SUM in unit time, then it would be easy to solve SUBSET-SUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonempty set.

It is also NP-easy. If we had a black box that solved SUBSET-SUM in unit time, then we could use it to solve FIND-SUBSET-SUM. If it returns false, we immediately return the empty set. Otherwise, we visit each element in order and remove it provided that SUBSET-SUM would still return true after we remove it. Once we've visited every element, we will no longer be able to remove any element without changing the answer from true to false; at this point the remaining subset of the original elements must sum to zero. This requires us to note that later removals of elements do not alter the fact that removal of an earlier element changed the answer from true to false. In pseudocode:

function FIND-SUBSET-SUM(set S)    if not(SUBSET-SUM(S)) return {} for each x in S        if SUBSET-SUM(S – {x}) S := S – {x} return S

Another well-known NP-equivalent problem is the traveling salesman problem.

Clarification
In this context NP stands for nondeterministic polynomial time. There are also NP-equivalence classes of Boolean functions, where NP stands for negation and permutation.

title: NP-equivalent


text:
Direct-access storage device

A direct-access storage device (DASD) (pronounced ) is a secondary storage device in which "each physical record has a discrete location and a unique address". The term was coined by IBM to describe devices that allowed random access to data, the main examples being drum memory and hard disk drives. Later, optical disc drives and flash memory units are also classified as DASD.

The term DASD contrasts with sequential access storage device such as a magnetic tape drive, and unit record equipment such as a punched card device. A record on a DASD can be accessed without having to read through intervening records from the current location, whereas reading anything other than the "next" record on tape or deck of cards requires skipping over intervening records, and requires a proportionally long time to access a distant point in a medium. Access methods for DASD include sequential, partitioned, indexed, and direct.

The DASD storage class includes both fixed and removable media.

Architecture
IBM mainframes access I/O devices including DASD through channels, a type of subordinate mini-processor. Channel programs write to, read from, and control the given device.

CTR (CHR)
The operating system uses a four byte relative track and record (TTR) for some access methods and for others an eight-byte extent-bin-cylinder-track-record block address, or MBBCCHHR, Channel programs address DASD using a six byte seek address (BBCCHH) and a five byte record  identifier (CCHHR). When the 2321 data cell was discontinued in January 1975, the addressing scheme and the device itself was referred to as CHR or CTR for cylinder-track-record, as the bin number was always 0.
 * M represents the extent number within the allocation
 * BB representing the Bin (from 2321 data cells),
 * CC representing the Cylinder,
 * HH representing the Head (or track), and
 * R representing the Record (block) number.

IBM refers to the data records programmers work with as logical records, and the format on DASD as blocks or physical records. One block might contain several logical (or user) records or, in some schemes, called spanned records, partial logical records.

Physical records can have any size up to the limit of a track, but some devices have a track overflow feature that allows breaking a large block into track-size segments within the same cylinder.

The queued access methods, such as QSAM, are responsible for blocking and deblocking logical records as they are written to or read from external media. The basic access methods, such as BSAM, require the user program to do it.

CKD
CKD is an acronym for Count Key Data, the physical layout of a block on a DASD device, and should not be confused with BBCCH and CCHHR, which are the addresses used by the channel program. CTR in this context may refer to either type of address, depending on the channel command.

FBA
In 1979 IBM introduced fixed block architecture (FBA) for mainframes. At the programming level, these devices do not use the traditional CHR addressing, but reference fixed-length blocks by number, much like sectors in mini-computers. More correctly, the application programmer remains unaware of the underlying storage arrangement, which stores the data in fixed physical block lengths of 512, 1024, 2048, or 4096, depending on the device type. As part of the FBA interface IBM introduced new channel commands for asynchronous operation that are very similar to those introduced for ECKD. For some applications, FBA not only offers simplicity, but an increase in throughput.

FBA is supported by VM/370 and DOS/VSE, but not MVS or successor operating systems in the OS/360 line.

FCP attached SCSI
Processors with FICON channels can access SCSI drives using Fibre Channel Protocol (FCP). While z/VM and z/VSE fully support FCP, z/OS provides only limited support through IOSFBA.

Access
Some programming interface macros and routines are collectively referred to as access methods with names ending in A ccess M ethod.

DOS/360 and successors
DOS/360 through z/VSE support datasets on DASD with the following access methods:
 * Logical IOCS (LIOCS)
 * sequential access method (SAM)
 * direct access method (DAM)
 * indexed sequential access method (ISAM)
 * virtual storage access method (VSAM)
 * Physical IOCS (PIOCS)
 * Execute channel program (EXCP)

OS/360 and successors
OS/360 through z/OS support datasets on DASD with the following access methods:
 * Basic sequential access method (BSAM)
 * Basic indexed sequential access method (BISAM)
 * Queued sequential access method (QSAM)
 * Queued indexed sequential access method (QISAM)
 * Basic partitioned access method (BPAM)
 * Basic direct access method (BDAM)
 * Virtual storage access method (VSAM)
 * Execute Channel Program (EXCP)
 * Execute Channel Program in Real Storage (EXCPVR)

In MVS, starting with OS/VS2 Release 2 and continuing through z/OS, all of the access methods including EXCP[ VR], use the privileged STARTIO macro.

Terminology
IBM in its 1964 first version of the "IBM System/360 System Summary" used the term File to collectively described devices now called DASD. Files provided "random access storage'" At the same time IBM's product reference manual described such devices as "direct access storage devices " without any acronym.

An early public use of the acronym DASD is in IBM's March 1966 manual, "Data File Handbook. " The earliest non-IBM use of the acronym DASD found by the "Google ngram viewer" to refer to storage devices dates from 1968. From then on use of the term grew exponentially until 1990 after which its usage declined substantially.

Both drums and data cells have disappeared as products, so DASD remains as a synonym of disk, flash and optical devices. Modern DASD used in mainframes only very rarely consist of single disk-drives. Most commonly "DASD" means large disk arrays utilizing RAID schemes. Current devices emulate CKD on FBA hardware.

title: Direct-access storage device


text:
Hyde Park

Hyde Park may refer to:

England

 * Hyde Park, London, a Royal Park in Central London
 * Hyde Park, Leeds, an inner-city area of north-west Leeds
 * Hyde Park, Sheffield, district of Sheffield
 * Hyde Park, in Hyde, Greater Manchester

Australia

 * Hyde Park, Perth, a park in Perth
 * Hyde Park, Queensland, a suburb of Townsville
 * Hyde Park, South Australia, a suburb of Adelaide
 * Hyde Park, Sydney, park in New South Wales

United States

 * Hyde Park, Los Angeles, California
 * Hyde Park (Tampa), Florida
 * Hyde Park, Boise, Idaho, a historic district in Boise's North End neighborhood
 * Hyde Park, Chicago, Illinois, a neighborhood
 * Hyde Park Township, Cook County, Illinois, annexed by Chicago in 1889
 * Hyde Park, Boston, Massachusetts
 * Hyde Park Township, Wabasha County, Minnesota
 * Hyde Park, Kansas City, Missouri
 * Hyde Park, St. Louis, Missouri
 * Hyde Park, New Mexico
 * Hyde Park, Cincinnati, Ohio
 * Woodbourne-Hyde Park, Ohio
 * Hyde Park, Pennsylvania, borough in Westmoreland County
 * Hyde Park, Berks County, Pennsylvania
 * Hyde Park (Hato Rey), a subbarrio of Hato Rey Sur, San Juan, Puerto Rico
 * Hyde Park, Memphis, Tennessee
 * Hyde Park (Austin, Texas)
 * Hyde Park, Montrose, Houston, Texas
 * Hyde Park, Utah
 * Hyde Park, Georgia

New York

 * Hyde Park, New York, town in Dutchess County, New York, hometown of Franklin D. Roosevelt
 * Hyde Park (CDP), New York, a hamlet and census-designated place (CDP) in the town of Hyde Park
 * Hyde Park (hamlet), New York, a hamlet in Otsego County, New York
 * New Hyde Park, New York, Long Island

Vermont

 * Hyde Park (town), Vermont
 * Hyde Park (village), Vermont
 * North Hyde Park, Vermont

Other countries

 * Hyde Park, Guyana, in the Demerara-Mahaica Region
 * Hyde Park, Gauteng, South Africa
 * Hyde Park, Belgrade, Serbia

Grounds

 * Hyde Park, Glasgow, a former football ground in Glasgow, Scotland
 * Dr. Hyde Park, a Gaelic Games ground in Roscommon, Ireland
 * Hyde Park (cricket ground), a former important cricket venue in Sheffield
 * Hyde Park (Niagara Falls, New York), a park in Niagara Falls, New York
 * Hyde Park (Burkeville, Virginia), a historic home and farm

Schools

 * Hyde Park Career Academy, Chicago, Illinois, United States
 * Hyde Park High School (South Africa)
 * Hyde Park Junior School, United Kingdom
 * Hyde Park Baptist High School, Austin, Texas, United States
 * Hyde Park Middle School, Las Vegas, Nevada, United States

Other uses

 * Hyde Park (play), by James Shirley
 * Hyde Park (1934 film), a British comedy film
 * Hyde Park (2017 film), an independent Western film
 * Hyde Park Movement Party, Thailand
 * Hyde Park Diggers, London hippie movement and commune co-founded by Sid Rawle
 * Hyde Park Theatre, an arts center in Austin, Texas
 * Hyde Park (Osnabrück), a music venue

title: Hyde Park


text:
EXPTIME

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds.

EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space.

EXPTIME relates to the other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem and the space hierarchy theorem, it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE.

Formal definition
In terms of DTIME,

Relationships to other classes
It is known that

and also, by the time hierarchy theorem and the space hierarchy theorem, that

In the above expressions, the symbol ⊆ means "is a subset of", and the symbol ⊊ means "is a strict subset of".

so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are. It is also known that if P = NP, then EXPTIME = NEXPTIME, the class of problems solvable in exponential time by a nondeterministic Turing machine. More precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.

EXPTIME can be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. This is one way to see that PSPACE ⊆ EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.

EXPTIME-complete
A decision problem is EXPTIME-complete if it is in EXPTIME and every problem in EXPTIME has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. Problems that are EXPTIME-complete might be thought of as the hardest problems in EXPTIME. Notice that although it is unknown whether NP is equal to P, we do know that EXPTIME-complete problems are not in P; it has been proven that these problems cannot be solved in polynomial time, by the time hierarchy theorem.

In computability theory, one of the basic undecidable problems is the halting problem: deciding whether a deterministic Turing machine (DTM) halts. One of the most fundamental EXPTIME-complete problems is a simpler version of this, which asks if a DTM halts on a given input in at most k steps. It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more. The same problem with the number of steps written in unary is P-complete.

Other examples of EXPTIME-complete problems include the problem of evaluating a position in generalized chess, checkers, or Go (with Japanese ko rules). These games have a chance of being EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. In the Go example, the Japanese ko rule is known to imply EXPTIME-completeness, but it is not known if the American or Chinese rules for the game are EXPTIME-complete (they could range from PSPACE to EXPSPACE).

By contrast, generalized games that can last for a number of moves that is polynomial in the size of the board are often PSPACE-complete. The same is true of exponentially long games in which non-repetition is automatic.

Another set of important EXPTIME-complete problems relates to succinct circuits. Succinct circuits are simple machines used to describe some graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. For many natural P-complete graph problems, where the graph is expressed in a natural representation such as an adjacency matrix, solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller; but this requires nontrivial proof, since succinct circuits can only describe a subclass of graphs.

title: EXPTIME


text:
RAID

RAID ("redundant array of inexpensive disks" or "redundant array of independent disks" ) is a data storage virtualization technology that combines multiple physical disk drive components into one or more logical units for the purposes of data redundancy, performance improvement, or both. This is in contrast to the previous concept of highly reliable mainframe disk drives referred to as "single large expensive disk" (SLED).

Data is distributed across the drives in one of several ways, referred to as RAID levels, depending on the required level of redundancy and performance. The different schemes, or data distribution layouts, are named by the word "RAID" followed by a number, for example RAID 0 or RAID 1. Each scheme, or RAID level, provides a different balance among the key goals: reliability, availability, performance, and capacity. RAID levels greater than RAID 0 provide protection against unrecoverable sector read errors, as well as against failures of whole physical drives.

History
The term "RAID" was invented by David Patterson, Garth Gibson, and Randy Katz at the University of California, Berkeley in 1987. In their June 1988 paper "A Case for Redundant Arrays of Inexpensive Disks (RAID)", presented at the SIGMOD Conference, they argued that the top-performing mainframe disk drives of the time could be beaten on performance by an array of the inexpensive drives that had been developed for the growing personal computer market. Although failures would rise in proportion to the number of drives, by configuring for redundancy, the reliability of an array could far exceed that of any large single drive.

Although not yet using that terminology, the technologies of the five levels of RAID named in the June 1988 paper were used in various products prior to the paper's publication, including the following:

 * Mirroring (RAID 1) was well established in the 1970s including, for example, Tandem NonStop Systems.
 * In 1977, Norman Ken Ouchi at IBM filed a patent disclosing what was subsequently named RAID 4.
 * Around 1983, DEC began shipping subsystem mirrored RA8X disk drives (now known as RAID 1) as part of its HSC50 subsystem.
 * In 1986, Clark et al. at IBM filed a patent disclosing what was subsequently named RAID 5.
 * Around 1988, the Thinking Machines' DataVault used error correction codes (now known as RAID 2) in an array of disk drives. A similar approach was used in the early 1960s on the IBM 353.

Industry manufacturers later redefined the RAID acronym to stand for "redundant array of independent disks".

Overview
Many RAID levels employ an error protection scheme called "parity", a widely used method in information technology to provide fault tolerance in a given set of data. Most use simple XOR, but RAID 6 uses two separate parities based respectively on addition and multiplication in a particular Galois field or Reed–Solomon error correction.

RAID can also provide data security with solid-state drives (SSDs) without the expense of an all-SSD system. For example, a fast SSD can be mirrored with a mechanical drive. For this configuration to provide a significant speed advantage, an appropriate controller is needed that uses the fast SSD for all read operations. Adaptec calls this "hybrid RAID".

Standard levels
Originally, there were five standard levels of RAID, but many variations have evolved, including several nested levels and many non-standard levels (mostly proprietary). RAID levels and their associated data formats are standardized by the Storage Networking Industry Association (SNIA) in the Common RAID Disk Drive Format (DDF) standard:

 * RAID 0 consists of block-level striping, but no mirroring or parity. Compared to a spanned volume, the capacity of a RAID 0 volume is the same; it is the sum of the capacities of the drives in the set. But because striping distributes the contents of each file among all drives in the set, the failure of any drive causes the entire RAID 0 volume and all files to be lost. In comparison, a spanned volume preserves the files on the unfailing drives. The benefit of RAID 0 is that the throughput of read and write operations to any file is multiplied by the number of drives because, unlike spanned volumes, reads and writes are done concurrently. The cost is increased vulnerability to drive failures—since any drive in a RAID 0 setup failing causes the entire volume to be lost, the average failure rate of the volume rises with the number of attached drives.
 * RAID 1 consists of data mirroring, without parity or striping. Data is written identically to two or more drives, thereby producing a "mirrored set" of drives. Thus, any read request can be serviced by any drive in the set. If a request is broadcast to every drive in the set, it can be serviced by the drive that accesses the data first (depending on its seek time and rotational latency), improving performance. Sustained read throughput, if the controller or software is optimized for it, approaches the sum of throughputs of every drive in the set, just as for RAID 0. Actual read throughput of most RAID 1 implementations is slower than the fastest drive. Write throughput is always slower because every drive must be updated, and the slowest drive limits the write performance. The array continues to operate as long as at least one drive is functioning.
 * RAID 2 consists of bit-level striping with dedicated Hamming-code parity. All disk spindle rotation is synchronized and data is striped such that each sequential bit is on a different drive. Hamming-code parity is calculated across corresponding bits and stored on at least one parity drive. This level is of historical significance only; although it was used on some early machines (for example, the Thinking Machines CM-2), it is not used by any commercially available system.
 * RAID 3 consists of byte-level striping with dedicated parity. All disk spindle rotation is synchronized and data is striped such that each sequential byte is on a different drive. Parity is calculated across corresponding bytes and stored on a dedicated parity drive. Although implementations exist, RAID 3 is not commonly used in practice.
 * RAID 4 consists of block-level striping with dedicated parity. This level was previously used by NetApp, but has now been largely replaced by a proprietary implementation of RAID 4 with two parity disks, called RAID-DP. The main advantage of RAID 4 over RAID 2 and 3 is I/O parallelism: in RAID 2 and 3, a single read I/O operation requires reading the whole group of data drives, while in RAID 4 one I/O read operation does not have to spread across all data drives. As a result, more I/O operations can be executed in parallel, improving the performance of small transfers.
 * RAID 5 consists of block-level striping with distributed parity. Unlike RAID 4, parity information is distributed among the drives, requiring all drives but one to be present to operate. Upon failure of a single drive, subsequent reads can be calculated from the distributed parity such that no data is lost. RAID 5 requires at least three disks. Like all single-parity concepts, large RAID 5 implementations are susceptible to system failures because of trends regarding array rebuild time and the chance of drive failure during rebuild (see "Increasing rebuild time and failure probability" section, below). Rebuilding an array requires reading all data from all disks, opening a chance for a second drive failure and the loss of the entire array.
 * RAID 6 consists of block-level striping with double distributed parity. Double parity provides fault tolerance up to two failed drives. This makes larger RAID groups more practical, especially for high-availability systems, as large-capacity drives take longer to restore. RAID 6 requires a minimum of four disks. As with RAID 5, a single drive failure results in reduced performance of the entire array until the failed drive has been replaced. With a RAID 6 array, using drives from multiple sources and manufacturers, it is possible to mitigate most of the problems associated with RAID 5. The larger the drive capacities and the larger the array size, the more important it becomes to choose RAID 6 instead of RAID 5. RAID 10 also minimizes these problems.

Nested (hybrid) RAID
In what was originally termed hybrid RAID, many storage controllers allow RAID levels to be nested. The elements of a RAID may be either individual drives or arrays themselves. Arrays are rarely nested more than one level deep.

The final array is known as the top array. When the top array is RAID 0 (such as in RAID 1+0 and RAID 5+0), most vendors omit the "+" (yielding RAID 10 and RAID 50, respectively).

 * RAID 0+1: creates two stripes and mirrors them. If a single drive failure occurs then one of the mirrors has failed, at this point it is running effectively as RAID 0 with no redundancy. Significantly higher risk is introduced during a rebuild than RAID 1+0 as all the data from all the drives in the remaining stripe has to be read rather than just from one drive, increasing the chance of an unrecoverable read error (URE) and significantly extending the rebuild window.
 * RAID 1+0: (see: RAID 10) creates a striped set from a series of mirrored drives. The array can sustain multiple drive losses so long as no mirror loses all its drives.
 * JBOD RAID N+N: With JBOD (just a bunch of disks), it is possible to concatenate disks, but also volumes such as RAID sets. With larger drive capacities, write delay and rebuilding time increase dramatically (especially, as described above, with RAID 5 and RAID 6). By splitting a larger RAID N set into smaller subsets and concatenating them with linear JBOD, write and rebuilding time will be reduced. If a hardware RAID controller is not capable of nesting linear JBOD with RAID N, then linear JBOD can be achieved with OS-level software RAID in combination with separate RAID N subset volumes created within one, or more, hardware RAID controller(s). Besides a drastic speed increase, this also provides a substantial advantage: the possibility to start a linear JBOD with a small set of disks and to be able to expand the total set with disks of different size, later on (in time, disks of bigger size become available on the market). There is another advantage in the form of disaster recovery (if a RAID N subset happens to fail, then the data on the other RAID N subsets is not lost, reducing restore time).

Non-standard levels
Many configurations other than the basic numbered RAID levels are possible, and many companies, organizations, and groups have created their own non-standard configurations, in many cases designed to meet the specialized needs of a small niche group. Such configurations include the following:

 * Linux MD RAID 10 provides a general RAID driver that in its "near" layout defaults to a standard RAID 1 with two drives, and a standard RAID 1+0 with four drives; however, it can include any number of drives, including odd numbers. With its "far" layout, MD RAID 10 can run both striped and mirrored, even with only two drives in  layout; this runs mirroring with striped reads, giving the read performance of RAID 0. Regular RAID 1, as provided by Linux software RAID, does not stripe reads, but can perform reads in parallel.
 * Hadoop has a RAID system that generates a parity file by xor-ing a stripe of blocks in a single HDFS file.
 * BeeGFS, the parallel file system, has internal striping (comparable to file-based RAID0) and replication (comparable to file-based RAID10) options to aggregate throughput and capacity of multiple servers and is typically based on top of an underlying RAID to make disk failures transparent.
 * Declustered RAID scatters dual (or more) copies of the data across all disks (possibly hundreds) in a storage subsystem, while holding back enough spare capacity to allow for a few disks to fail. The scattering is based on algorithms which give the appearance of arbitrariness. When one or more disks fail the missing copies are rebuilt into that spare capacity, again arbitrarily. Because the rebuild is done from and to all the remaining disks, it operates much faster than with traditional RAID, reducing the overall impact on clients of the storage system.

Implementations
The distribution of data across multiple drives can be managed either by dedicated computer hardware or by software. A software solution may be part of the operating system, part of the firmware and drivers supplied with a standard drive controller (so-called "hardware-assisted software RAID"), or it may reside entirely within the hardware RAID controller.

Hardware-based
Hardware RAID controllers can be configured through card BIOS or Option ROM before an operating system is booted, and after the operating system is booted, proprietary configuration utilities are available from the manufacturer of each controller. Unlike the network interface controllers for Ethernet, which can usually be configured and serviced entirely through the common operating system paradigms like ifconfig in Unix, without a need for any third-party tools, each manufacturer of each RAID controller usually provides their own proprietary software tooling for each operating system that they deem to support, ensuring a vendor lock-in, and contributing to reliability issues.

For example, in FreeBSD, in order to access the configuration of Adaptec RAID controllers, users are required to enable Linux compatibility layer, and use the Linux tooling from Adaptec, potentially compromising the stability, reliability and security of their setup, especially when taking the long-term view.

Some other operating systems have implemented their own generic frameworks for interfacing with any RAID controller, and provide tools for monitoring RAID volume status, as well as facilitation of drive identification through LED blinking, alarm management and hot spare disk designations from within the operating system without having to reboot into card BIOS. For example, this was the approach taken by OpenBSD in 2005 with its bio(4) pseudo-device and the bioctl utility, which provide volume status, and allow LED/alarm/hotspare control, as well as the sensors (including the drive sensor) for health monitoring; this approach has subsequently been adopted and extended by NetBSD in 2007 as well.

Software-based
Software RAID implementations are provided by many modern operating systems. Software RAID can be implemented as:
 * A layer that abstracts multiple devices, thereby providing a single virtual device (such as Linux kernel's md and OpenBSD's softraid)
 * A more generic logical volume manager (provided with most server-class operating systems such as Veritas or LVM)
 * A component of the file system (such as ZFS, Spectrum Scale or Btrfs)
 * A layer that sits above any file system and provides parity protection to user data (such as RAID-F)

Some advanced file systems are designed to organize data across multiple storage devices directly, without needing the help of a third-party logical volume manager:
 * ZFS supports the equivalents of RAID 0, RAID 1, RAID 5 (RAID-Z1) single-parity, RAID 6 (RAID-Z2) double-parity, and a triple-parity version (RAID-Z3) also referred to as RAID 7. As it always stripes over top-level vdevs, it supports equivalents of the 1+0, 5+0, and 6+0 nested RAID levels (as well as striped triple-parity sets) but not other nested combinations. ZFS is the native file system on Solaris and illumos, and is also available on FreeBSD and Linux. Open-source ZFS implementations are actively developed under the OpenZFS umbrella project.
 * Spectrum Scale, initially developed by IBM for media streaming and scalable analytics, supports declustered RAID protection schemes up to n+3. A particularity is the dynamic rebuilding priority which runs with low impact in the background until a data chunk hits n+0 redundancy, in which case this chunk is quickly rebuilt to at least n+1. On top, Spectrum Scale supports metro-distance RAID 1.
 * Btrfs supports RAID 0, RAID 1 and RAID 10 (RAID 5 and 6 are under development).
 * XFS was originally designed to provide an integrated volume manager that supports concatenating, mirroring and striping of multiple physical storage devices. However, the implementation of XFS in Linux kernel lacks the integrated volume manager.

Many operating systems provide RAID implementations, including the following:
 * Hewlett-Packard's OpenVMS operating system supports RAID 1. The mirrored disks, called a "shadow set", can be in different locations to assist in disaster recovery.
 * Apple's macOS and macOS Server support RAID 0, RAID 1, and RAID 1+0.
 * FreeBSD supports RAID 0, RAID 1, RAID 3, and RAID 5, and all nestings via GEOM modules and ccd.
 * Linux's md supports RAID 0, RAID 1, RAID 4, RAID 5, RAID 6, and all nestings. Certain reshaping/resizing/expanding operations are also supported.
 * Microsoft Windows supports RAID 0, RAID 1, and RAID 5 using various software implementations. Logical Disk Manager, introduced with Windows 2000, allows for the creation of RAID 0, RAID 1, and RAID 5 volumes by using dynamic disks, but this was limited only to professional and server editions of Windows until the release of Windows 8. Windows XP can be modified to unlock support for RAID 0, 1, and 5. Windows 8 and Windows Server 2012 introduced a RAID-like feature known as Storage Spaces, which also allows users to specify mirroring, parity, or no redundancy on a folder-by-folder basis. These options are similar to RAID 1 and RAID 5, but are implemented at a higher abstraction level.
 * NetBSD supports RAID 0, 1, 4, and 5 via its software implementation, named RAIDframe.
 * OpenBSD supports RAID 0, 1 and 5 via its software implementation, named softraid.

If a boot drive fails, the system has to be sophisticated enough to be able to boot from the remaining drive or drives. For instance, consider a computer whose disk is configured as RAID 1 (mirrored drives); if the first drive in the array fails, then a first-stage boot loader might not be sophisticated enough to attempt loading the second-stage boot loader from the second drive as a fallback. The second-stage boot loader for FreeBSD is capable of loading a kernel from such an array.

Firmware- and driver-based

Software-implemented RAID is not always compatible with the system's boot process, and it is generally impractical for desktop versions of Windows. However, hardware RAID controllers are expensive and proprietary. To fill this gap, inexpensive "RAID controllers" were introduced that do not contain a dedicated RAID controller chip, but simply a standard drive controller chip, or the chipset built-in RAID function, with proprietary firmware and drivers. During early bootup, the RAID is implemented by the firmware and, once the operating system has been more completely loaded, the drivers take over control. Consequently, such controllers may not work when driver support is not available for the host operating system. An example is Intel Rapid Storage Technology, implemented on many consumer-level motherboards.

Because some minimal hardware support is involved, this implementation is also called "hardware-assisted software RAID", "hybrid model" RAID, or even "fake RAID". If RAID 5 is supported, the hardware may provide a hardware XOR accelerator. An advantage of this model over the pure software RAID is that—if using a redundancy mode—the boot drive is protected from failure (due to the firmware) during the boot process even before the operating system's drivers take over.

Integrity
Data scrubbing (referred to in some environments as patrol read) involves periodic reading and checking by the RAID controller of all the blocks in an array, including those not otherwise accessed. This detects bad blocks before use. Data scrubbing checks for bad blocks on each storage device in an array, but also uses the redundancy of the array to recover bad blocks on a single drive and to reassign the recovered data to spare blocks elsewhere on the drive.

Frequently, a RAID controller is configured to "drop" a component drive (that is, to assume a component drive has failed) if the drive has been unresponsive for eight seconds or so; this might cause the array controller to drop a good drive because that drive has not been given enough time to complete its internal error recovery procedure. Consequently, using consumer-marketed drives with RAID can be risky, and so-called "enterprise class" drives limit this error recovery time to reduce risk. Western Digital's desktop drives used to have a specific fix. A utility called WDTLER.exe limited a drive's error recovery time. The utility enabled TLER (time limited error recovery), which limits the error recovery time to seven seconds. Around September 2009, Western Digital disabled this feature in their desktop drives (such as the Caviar Black line), making such drives unsuitable for use in RAID configurations. However, Western Digital enterprise class drives are shipped from the factory with TLER enabled. Similar technologies are used by Seagate, Samsung, and Hitachi. For non-RAID usage, an enterprise class drive with a short error recovery timeout that cannot be changed is therefore less suitable than a desktop drive. In late 2010, the Smartmontools program began supporting the configuration of ATA Error Recovery Control, allowing the tool to configure many desktop class hard drives for use in RAID setups.

While RAID may protect against physical drive failure, the data is still exposed to operator, software, hardware, and virus destruction. Many studies cite operator fault as a common source of malfunction, such as a server operator replacing the incorrect drive in a faulty RAID, and disabling the system (even temporarily) in the process.

An array can be overwhelmed by catastrophic failure that exceeds its recovery capacity and the entire array is at risk of physical damage by fire, natural disaster, and human forces, however backups can be stored off site. An array is also vulnerable to controller failure because it is not always possible to migrate it to a new, different controller without data loss.

Correlated failures
In practice, the drives are often the same age (with similar wear) and subject to the same environment. Since many drive failures are due to mechanical issues (which are more likely on older drives), this violates the assumptions of independent, identical rate of failure amongst drives; failures are in fact statistically correlated. In practice, the chances for a second failure before the first has been recovered (causing data loss) are higher than the chances for random failures. In a study of about 100,000 drives, the probability of two drives in the same cluster failing within one hour was four times larger than predicted by the exponential statistical distribution—which characterizes processes in which events occur continuously and independently at a constant average rate. The probability of two failures in the same 10-hour period was twice as large as predicted by an exponential distribution.

Unrecoverable read errors during rebuild
Unrecoverable read errors (URE) present as sector read failures, also known as latent sector errors (LSE). The associated media assessment measure, unrecoverable bit error (UBE) rate, is typically guaranteed to be less than one bit in 1015 for enterprise-class drives (SCSI, FC, SAS or SATA), and less than one bit in 1014 for desktop-class drives (IDE/ATA/PATA or SATA). Increasing drive capacities and large RAID 5 instances have led to the maximum error rates being insufficient to guarantee a successful recovery, due to the high likelihood of such an error occurring on one or more remaining drives during a RAID set rebuild. When rebuilding, parity-based schemes such as RAID 5 are particularly prone to the effects of UREs as they affect not only the sector where they occur, but also reconstructed blocks using that sector for parity computation.

Double-protection parity-based schemes, such as RAID 6, attempt to address this issue by providing redundancy that allows double-drive failures; as a downside, such schemes suffer from elevated write penalty—the number of times the storage medium must be accessed during a single write operation. Schemes that duplicate (mirror) data in a drive-to-drive manner, such as RAID 1 and RAID 10, have a lower risk from UREs than those using parity computation or mirroring between striped sets. Data scrubbing, as a background process, can be used to detect and recover from UREs, effectively reducing the risk of them happening during RAID rebuilds and causing double-drive failures. The recovery of UREs involves remapping of affected underlying disk sectors, utilizing the drive's sector remapping pool; in case of UREs detected during background scrubbing, data redundancy provided by a fully operational RAID set allows the missing data to be reconstructed and rewritten to a remapped sector.

Increasing rebuild time and failure probability
Drive capacity has grown at a much faster rate than transfer speed, and error rates have only fallen a little in comparison. Therefore, larger-capacity drives may take hours if not days to rebuild, during which time other drives may fail or yet undetected read errors may surface. The rebuild time is also limited if the entire array is still in operation at reduced capacity. Given an array with only one redundant drive (which applies to RAID levels 3, 4 and 5, and to "classic" two-drive RAID 1), a second drive failure would cause complete failure of the array. Even though individual drives' mean time between failure (MTBF) have increased over time, this increase has not kept pace with the increased storage capacity of the drives. The time to rebuild the array after a single drive failure, as well as the chance of a second failure during a rebuild, have increased over time.

Some commentators have declared that RAID 6 is only a "band aid" in this respect, because it only kicks the problem a little further down the road. However, according to the 2006 NetApp study of Berriman et al., the chance of failure decreases by a factor of about 3,800 (relative to RAID 5) for a proper implementation of RAID 6, even when using commodity drives. Nevertheless, if the currently observed technology trends remain unchanged, in 2019 a RAID 6 array will have the same chance of failure as its RAID 5 counterpart had in 2010.

Mirroring schemes such as RAID 10 have a bounded recovery time as they require the copy of a single failed drive, compared with parity schemes such as RAID 6, which require the copy of all blocks of the drives in an array set. Triple parity schemes, or triple mirroring, have been suggested as one approach to improve resilience to an additional drive failure during this large rebuild time.

Atomicity
A system crash or other interruption of a write operation can result in states where the parity is inconsistent with the data due to non-atomicity of the write process, such that the parity cannot be used for recovery in the case of a disk failure. This is commonly termed the write hole which is a known data corruption issue in older and low-end RAIDs, caused by interrupted destaging of writes to disk. The write hole can be addressed in a few ways:

 * Write-ahead logging.
 * Hardware RAID systems use an onboard nonvolatile cache for this purpose.
 * mdadm can use a dedicated journaling device (to avoid performance penalty, typically, SSDs and NVMs are preferred) for this purpose.
 * Write intent logging. mdadm uses a "write-intent-bitmap". If it finds any location marked as incompletely written at startup, it resyncs them. It closes the write hole but does not protect against loss of in-transit data, unlike a full WAL.
 * Partial parity. mdadm can save a "partial parity" that, when combined with modified chunks, recovers the original parity. This closes the write hole, but again does not protect against loss of in-transit data.
 * Dynamic stripe size. RAID-Z ensures that each block is its own stripe, so every block is complete. Copy-on-write (COW) transactional semantics guard metadata associated with stripes. The downside is IO fragmentation.
 * Avoiding overwriting used stripes. bcachefs, which uses a copying garbage collector, chooses this option. COW again protect references to striped data.

Write hole is a little understood and rarely mentioned failure mode for redundant storage systems that do not utilize transactional features. Database researcher Jim Gray wrote "Update in Place is a Poison Apple" during the early days of relational database commercialization.

Write-cache reliability
There are concerns about write-cache reliability, specifically regarding devices equipped with a write-back cache, which is a caching system that reports the data as written as soon as it is written to cache, as opposed to when it is written to the non-volatile medium. If the system experiences a power loss or other major failure, the data may be irrevocably lost from the cache before reaching the non-volatile storage. For this reason good write-back cache implementations include mechanisms, such as redundant battery power, to preserve cache contents across system failures (including power failures) and to flush the cache at system restart time.

title: RAID


text:
Talk:Fictional universe

Fictional universe vs. setting
The fact that you have to keep drawing this line demonstrates that it's arbitrary. There is no qualitative difference between the fictional universe of Tales of the City and the fictional universe of Tales of the Beanworld; it's only a quantitative matter of degree. They're all fictional universes... just some are more fictional (and more elaborate) than others. - Jason A. Quest (talk) 00:37, 11 April 2009 (UTC)
 * If we go by your interpretation, then a fictional universe is no different from a setting, and this article may as well not exist. I think a fictional universe differs from a normal setting mainly in detail. If care has been taken to establish the setting's history, geography and physical rules then it is a fictional universe. These rules have to be consistent within the universe and, if other fictional works are set in that same universe, those must be consistent with them too. It may be OR to make such a claim, but it's also OR to make the claim that a fictional universe and a setting are interchangeable. So we lose either way. What we need is some lit-crit material on the subject. Serendi pod  ous  07:53, 31 May 2009 (UTC)
 * Lacking that, how about we go with the literal meaning of the words rather than proceeding from your personal definition? You can say "there must be some difference from setting" as many times as you want, but that doesn't make it so, and your insistence on pulling one out of thin air is getting tiresome. Adding the phrase "a fictional universe must..." is the worst kind of OR; the purpose of an encyclopedia is to describe, not to set rules. - Jason A. Quest (talk) 13:34, 31 May 2009 (UTC)
 * If you feel that way, then this article should just be merged with setting. And I'm not suggesting that would necessarily be the wrong thing to do. But such a merge would in itself would be an interpretation, and I'd like some discussion before it happens.  Serendi pod ous  13:36, 31 May 2009 (UTC)

 * Tales of the City relies heavily on readers' knowledge of the real San Francisco. Is that not a qualitative difference from Beanworld? —Tamfang (talk) 06:56, 26 October 2010 (UTC)

 * I agree there is a fundamental difference. More importantly, it is a concept - a literary theory, in fact - that some people use to discuss fiction. For example, by saying that in Tom Clancy's "Ryanverse" the shooting of Pope John Paul II occurred in 1982, not in 1981 as in our universe. I think what is missing from this article is a critique. In fact, Clancy simply changed the date to fit in with his pre-existing fictional chronology. There is no need to conceptualise a parallel universe. Equally, the fact that Superman and Wonderwoman have a tete-a-tete in a cartoon does not mean they are in the same universe. It just means that's the way the author told the story. This is totally different from talking about setting.--Jack Upland (talk) 20:38, 20 May 2020 (UTC)

Merge with Setting (fiction)
If there is no distinction between these two terms, as this article currently implies, then there is no need for two separate articles.  Serendi pod ous  13:49, 31 May 2009 (UTC)
 * Correction: The clear bright line that you insist on using to define whether something "qualifies" as a fictional universe (it must do this, it must have that) is not an objective one. That doesn't necessarily mean that this is the same topic as the other. - Jason A. Quest (talk) 16:18, 31 May 2009 (UTC)
 * The article, as it currently stands, makes no distinction whatsoever, clear or subjective. It is describing a fictional setting, nothing more, nothing less.  Serendi pod ous  17:17, 31 May 2009 (UTC)
 * If that's what happens when you remove your personal demands upon the subject, so be it. -Jason A. Quest (talk) 20:06, 31 May 2009 (UTC)
 * But then why isn't this article called "Setting"?  Serendi pod ous  20:14, 31 May 2009 (UTC)

12:39, 8 November 2009  Serendi pod ous  (←Redirected page to Setting (fiction))
 * There doesn't appear to be any established distinction between a fictional universe and a fictional setting, so the two don't really need to be distinct.  Serendi pod ous  13:47, 31 May 2009 (UTC)
 * Yes there is because a fictional universe is a complete different topic than fictional setting — Preceding unsigned comment added by 24.217.226.145 (talk • contribs)
 * Got a reference for that?  Serendi pod ous  03:09, 22 December 2009 (UTC)
 * I'm sure I may agree somewhat, but the argument is weak. Is there a tautologist in the house?  —Aladdin Sane (talk) 08:19, 22 December 2009 (UTC)
 * This is one of those times when Wikipedia really collapses as a resource. Everyone knows what a fictional universe is, everyone can explain what a fictional universe is, but no one (that I can find) has left a citation explaining what a fictional universe is. And until we can find one, we can't have an article on it.  Serendi pod ous  14:01, 22 December 2009 (UTC)

 * I undid the redirect. Not every fictional setting is a fictional universe.  Think of it is the level of detail.  And fictional settings can be in the real universe, most works of fiction happening in real world Earth after all.   D r e a m Focus  20:08, 25 January 2010 (UTC)
 * Sigh. Please explain, without resorting to original research, the difference between a fictional universe and a fictional setting, because right now the article makes no distinction between the two. I tried to make a distinction and my alterations were deleted as OR. But without OR there is no way to make a distinction.  Serendi pod ous  20:46, 25 January 2010 (UTC)
 * I've added something to try and make the distinction clear. It's OR, but without it there's no reason for this article to exist.  Serendi pod ous  21:04, 25 January 2010 (UTC)
 * The term fictional universe is found everywhere, not just as a standard naming policy for Wikipedia articles. A quick scan of Google book search shows it used in over two thousand books  and in the news search it appears as well.   D r e a m Focus  21:08, 25 January 2010 (UTC)
 * Do any of those sources explain what a fictional universe is?  Serendi pod ous  21:24, 25 January 2010 (UTC)
 * I'm sure they do. Do you doubt the definition presented in the article is valid?  I think the name itself is rather self explanatory.  See the article for Universe and read the first sentence there.  You can look up fictional as well if you have to.   D r e a m Focus  21:43, 25 January 2010 (UTC)
 * I wrote it so I don't think it's invalid. But if it's not cited, then it will be deleted, like it was last time.  Serendi pod ous  21:44, 25 January 2010 (UTC)
 * I doubt this article would have any chance of being deleted if it was ever sent to the AFD. Redirecting it without anyone noticing, is not the same as deleting it.   D r e a m Focus  21:47, 25 January 2010 (UTC)
 * What I mean is that all the material that marked out a fictional universe from a setting was removed as original research. I tried to put it back, but, as you can see above, I was shot down. So I merged it, because if I couldn't define a fictional universe, there was no point in having an article on it.  Serendi pod ous  21:53, 25 January 2010 (UTC)

 * I Googled for a definition and kept finding places that copied one from this Wikipedia article. Also found one strange alternate universe Wikipedia is in called Simple Wikipedia.  That's a good definition there. "A fictional universe is an made up world that is used as the setting for one or (more commonly) many works of fiction. It is often used in books but can be used in any form used to tell a story, for example role-playing games, television or movies. It can be said that every work of fiction makes a world of its own. A fictional universe is used when things in a story become a part either of other stories, or of games or other things."  We could use that definition.   D r e a m Focus  14:40, 26 January 2010 (UTC)
 * We can't use another wiki as a source. I really don't think we're going to find a source fit to Wikipedia standards, as I don't think this issue has been given much academic attention. For that reason I think this article either needs to remain uncited original research or re-merged.  Serendi pod ous  20:12, 26 January 2010 (UTC)
 * I was thinking the definition was one that could be used. It makes sense.  And nothing was merged, it just a redirect, and there no consensus to do that.  If you do not doubt it to be a real concept, then you shouldn't talk about getting rid of it.  The fact that so many Google news searches, Google book searches , and Google scholar searches even  call something a "fictional universe", and talk about it in this context, means it is clearly deserving an article.   D r e a m Focus  22:49, 26 January 2010 (UTC)
 * Those sources give many examples of what a fictional universe is, but not a definition of a fictional universe. The reason I redirected the article to "setting" is because without the specifics distinguishing the concept from "setting", which were removed as OR (because they are), there was no point in having this article.  Serendi pod ous  23:06, 26 January 2010 (UTC)

merge with setting
I pretty much agree this article hardly makes a difference between setting and fictional universe. At any case this whole article really needs citations. 190.140.251.85 (talk) 07:19, 14 December 2010 (UTC)
 * I'm reconciled that this article must exist in some form, given that Wikipedia itself uses the term in its policy statements. However, I would appreciate it if someone could determine exactly what a fictional universe is supposed to be.  Serendi pod ous  19:09, 14 December 2010 (UTC)
 * Some further explanation of the levels of canonicity that can exist in some of the more developed fictional universes might be helpful. I know this touches upon events like the Crisis on Infinite Earths - but there are some other interesting examples... The Dr Who Universe, the DC universe and the Alien/Predator universe spring to mind off the top of my head, all of which have evolved over decades across a variety of media via a plethora of authors/designers. To me, there's a subtle distinction between universes that take on a life of their own through usage by multiple authors in this way and well-defined settings that are largely the result of a single creator - like, say, Tolkien's Middle-Earth. Dybeck (talk) 21:58, 11 April 2012 (UTC)
 * "Shared universe" appears to be a subset of "fictional universe", so the implication is that not all fictional universes are shared.  Serendi pod ous  22:14, 11 April 2012 (UTC)

Aren't All Universes in Literature Fictional?
The biggest problem with trying to make distinctions about what is and what isn't a fictional universe is that, by definition, all fiction is made up. Merrian-Webster dictionary defines fiction as: "something invented by the imagination or feigned; specifically : an invented story." So trying to give qualitative value judgements on what is and what isn't is missing the point. I think the concept some of the editors are arguing for are more in line with alternative realities than fictional universes. You might think I am simply arguing semantics, but I think we're using an umbrella term that is so vague it has no meaning. People seem able to see that Star Wars is set in a fictional universe, but so is every Romance novel ever written, the only difference being Fabio isn't on the cover of The Empire Strikes Back, but the stories are still pure fantasy. Chalchiuhtlatonal (talk) 21:59, 22 February 2012 (UTC)
 * The problem is that there is this term "fictional universe" that is in wide circulation, and which many people consider worthy of a Wikipedia article. Wikipedia even has a policy on it. So it's quite clear we are dealing with something that is commonly understood. The problem is finding a written definition.  Serendi pod ous  23:28, 22 February 2012 (UTC)
 * Normally it refers to a series, not just a single novel.  D r e a m Focus  23:35, 22 February 2012 (UTC)

 * No, not all universes in literature are fictional, because it's not quite true that "all fiction is made up".  Consider Jane Austen's Persuasion, in which Anne Elliot visits Bath.  Anne Elliot is fictional.  Bath is not.  (Notice, for example, that on the page Persuasion (novel) there is a link to the article on Bath, Somerset -- it is not an article on a fictional city, but on the actual city.

 * The whole point of Jane Austen's books, or the Sherlock Holmes books, is to depict fictional characters in the real universe. The whole point of The Wizard of Oz or the Narnia books is to depict fictional characters who travel from the real universe to a fictional universe.

 * Of course, you might argue that the novel Persuasion depicts an imaginary England, completely identical to the real England except for the presence of a dozen fictional people. But that's not how these terms are used in ordinary speech.  In ordinary speech, the term "fictional universe" is not used to describe the setting of Jane Austen's novels. — Lawrence King ( talk ) 06:33, 7 August 2017 (UTC)

 * I agree. It's fundamentally different. You can critique The Hound of the Baskerville because its history and geography are wrong. You can't critique The Lord of the Rings in the same way. You might argue there are inconsistencies in Tolkien's world-building, but that's different.--Jack Upland (talk) 20:52, 20 May 2020 (UTC)

Joey and Seinfeld
I see that the reference to Joey and Seinfeld existing in the same universe has been removed and then reverted. I'll assume good faith for now, but can someone please find a citation for this, or remove it if this is not right? I was never a regular viewer of either series, but I'd never heard that. If Joey and Seinfeld are in the same universe, it follows that "Friends" and Seinfeld are in the same universe too, of course. The "Mad About You" reference is OK (via Ursula Buffay and Friends), but could also do with a citation. Dybeck (talk) 16:09, 2 June 2012 (UTC)
 * Paul Reiser's old apartment on Mad About You is now owned by Kramer. NBC likes liknking up its shows. It's all part of the Tommy Westphall universe.  Serendi pod ous  16:21, 2 June 2012 (UTC)
 * OK. I've tidied up the section and made it more relevant to the definition. It could still use a citation though if you can find one. Dybeck (talk) 12:25, 3 June 2012 (UTC)
 * This whole concept could use a citation.  Serendi pod ous  13:13, 3 June 2012 (UTC)

Markstein
Apparently, Don Markstein created and defined this term in a 1970 issue of CAPA-alpha (although when he archived the article on Toonopedia, he did mention the possibility that someone may have antedated him).

I feel that this is a valuable source which should be integrated into the article. DS (talk) 16:47, 31 May 2019 (UTC)

 * I think he also pioneered the concept, which is important to note.--Jack Upland (talk) 20:59, 20 May 2020 (UTC)

List of fictional counties up for deletion
I've added some sources. More are out there. Important literary device. Important list for some of our readers. 7&6=thirteen (☎) 12:00, 31 March 2020 (UTC)
 * Articles for deletion/List of fictional counties (3rd nomination)
 * Articles for deletion/List of fictional counties (3rd nomination)
 * Articles for deletion/List of fictional counties (3rd nomination)

Fillory?
Is Fillory a good example? It's a pretty direct parody of Narnia, and there's a bunch of better known fictional fantasy universes such as Middle Earth. — Preceding unsigned comment added by Resuna (talk • contribs) 16:34, 4 May 2020 (UTC)

POV
I have added a POV tag to this article because it only presents one side - that of fans who use the "fictional universe" concept. There should be a critique of this concept. It is not accepted by mainstream literary theory.--Jack Upland (talk) 21:04, 20 May 2020 (UTC)

 * I'm a bit late here, obviously, but just giving my unauthoratative opinion in the interest of resolving the tag, I'm not sure that that's a violation of WP:NPOV. Most of the article lists examples of fictional universes that are pretty unambiguous, as are most examples of fictional universes in the first place. On occasion, there are some examples of the subject that can be disputed (e.g. the "Tommy Westphall universe"), but they aren't mentioned on this page. I'm also not exactly sure what you mean by "not accepted by mainstream literary theory," but only by "fans of the concept." The definition given in the article is disputable depending on opinion, but at most that should be a section tag, and I personally find it fine. I don't know if "sides" really apply here. JœRunner talk / contribs 23:50, 5 June 2022 (UTC)
 * I have removed the tag, interpreting silence as consensus. Please reply to this with any objections. JœRunner talk / contribs 03:36, 15 September 2022 (UTC) — Preceding unsigned comment added by Gabldotink (talk • contribs)
 * I reiterate my objection. Saying you don't understand me is not an argument.--Jack Upland (talk) 03:50, 15 September 2022 (UTC)

Proposed merge of Fantasy world into Fictional universe
There seems to be very little distinction between a "fantasy world" and a fictional universe. Whether something is a "land", "world", or "universe" is largely semantic in nature, since it implies that the universe is different from our own. While the idea of a fictional universe was conceived later, it has become the de facto classification for such things as we have fully explored this world and stories set in unknown regions of it are no longer believable. It can be mentioned that past incarnations of fictional universes were known as "lands" or "worlds". ZXCVBNM (TALK) 14:33, 16 August 2021 (UTC)
 * Oppose: The two are not synonymous. The "Law and Order" universe is a fictional universe, but not a fantasy world. Not all fictional universes use magic or are inhabited by impossible creatures.  Serendi pod ous  16:12, 16 August 2021 (UTC)
 * Just because a fantasy world is a subgroup of fictional universe doesn't mean it requires its own article, especially since much of the information from both articles can safely be trimmed down as original research. A section on fictional universes in fantasy would be sufficient. ZXCVBNM (TALK) 18:55, 16 August 2021 (UTC)
 * Oppose The definition covered in the "fantasy world" article seems to cover countries, planets, or dimensions covered extensively in works of fantasy and science fiction. It even notes the lack of clear distinction between the two genres which use similar settings. The definition given in "fictional universe" seems to equate it with whatever is the main setting of a multimedia franchise. It discusses what effects the publishers and copyright-holders have on a franchise. Which frankly has nothing to do with the premise of a fantasy world. Dimadick (talk) 19:29, 16 August 2021 (UTC)
 * These are largely surmountable issues and the article also has things like "What distinguishes a fictional universe from a simple setting is the level of detail and internal consistency. A fictional universe has an established continuity and internal logic that must be adhered to throughout the work and even across separate works." That clearly also apply to fantasy worlds. If it was merged, it would be restructured to be less about the commercial franchise aspect and more about the overarching concept, including in fantasy. ZXCVBNM (TALK) 04:23, 17 August 2021 (UTC)
 * Oppose: A fictional universe does not necessarily require fantasy elements. Consider the famous Orwell work Nineteen Eighty-Four—it is lacking in many common fantasy elements, like parallel worlds, magic, mythological creatures, et cetera.  Much of the technology described existed even in Orwell's time, and much of his "Big Brother" exposition has proven remarkably prescient.  Orwell described a clearly fictional universe, but it could hardly be considered a fantastical one. 2601:3CA:204:F860:8D38:2607:4E8C:BAC2 (talk) 21:23, 26 August 2021 (UTC)
 * I would class 1984 as speculative fiction.--Jack Upland (talk) 05:28, 26 September 2021 (UTC)
 * Eventually oppose as well: Fictional universe is in Harry Potter and Percy Jackson. However they're not in fantasy world. Or maybe both can be merged, but the articles can be further improved without improving. Regards: Elan Morin Tedronai (talk)

Kennedy-Armstrong Meeting
This article claims that John F. Kennedy met Neil Armstrong. Do we actually have any evidence of this? I have seen reports that Neil Armstrong said that he never met John F. Kennedy. For example, see here: http://www.collectspace.com/ubb/Forum38/HTML/001883.html RomanSpa (talk) 11:04, 3 October 2023 (UTC)

title: Talk:Fictional universe


text:
Mani

Mani may refer to:

People

 * Mani (name),, a given name and surname (including a list of people with the name)
 * Mani (prophet) (c. 216 – 274), an Iranian prophet
 * Mani (musician) (born 1962), an English rock musician
 * Mani (actor) (born 1975), Pakistani film and television actor and host
 * Mani people, a Negrito ethnic group from Thailand

Geography

 * Mani, Bihar, a village in Bihar state of India
 * Maní, Casanare, a town and municipality in Casanare Department, Colombia
 * Mani, Chad, a town and sub-prefecture in Chad
 * Mani, Evros, a village in northeastern Greece
 * Mani, Karnataka, a village in Dakshina Kannada district of India
 * Mani, Iran, a village in Kerman Province, Iran
 * Mani, Nigeria, a town in Katsina State, Nigeria
 * Mani, Tibet, a village in the Tibet Autonomous Region of China
 * Maní, Yucatán, a small city in Yucatán, Mexico
 * East Mani, a municipality in the Laconia regional unit, Peloponnese, Greece
 * El Mani, a community on the island of Puerto Rico
 * Mani Peninsula, a geographical and cultural region in Greece
 * West Mani, a municipality in the Messenia regional unit, Peloponnese, Greece

Arts, entertainment, and media

 * Mani (web series), a 2017 Brat show
 * Mâni, a form of Turkish folk song
 * Mani: Travels in the Southern Peloponnese, a travelogue about the Greek peninsula by Patrick Leigh Fermor
 * Mani (film), a 2003 Indian Kannada-language romance film

Other uses

 * Maní (Amazonian legend), a legend of the indigenous tribe Tupi in Brazil
 * Máni, a personification of the moon in Norse mythology
 * Mani, short for the mantra of Avalokiteśvara, Om mani padme hum
 * Mani Jewel, any of various jewels mentioned in Buddhist literature
 * Manipur (disambiguation) (lit. 'jewel city'), various places in India
 * Al-Māniʿ, one of the names of God in Islam, meaning "Withholder" and "Defender".
 * Mani stick fighting, an African-derived martial art from Cuba
 * Mani the parakeet, a rose-ringed parakeet that serves as an astrologer "assistant" to M. Muniyappan in Singapore
 * Manicure, abbreviated "mani"
 * Mannosyl-oligosaccharide 1,2-alpha-mannosidase, an enzyme

title: Mani


text:
EXPSPACE

In computational complexity theory,  is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in $$O(2^{p(n)})$$ space, where $$p(n)$$ is a polynomial function of $$n$$. Some authors restrict $$p(n)$$ to be a linear function, but most authors instead call the resulting class. If we use a nondeterministic machine instead, we get the class, which is equal to by Savitch's theorem.

A decision problem is if it is in, and every problem in  has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in.

is a strict superset of, , and and is believed to be a strict superset of.

Formal definition
In terms of and ,

 * $$\mathsf{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}\left(2^{n^k}\right) = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}\left(2^{n^k}\right)$$

Examples of problems
An example of an problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression).

Alur and Henzinger extended linear temporal logic with times (integer) and prove that the validity problem of their logic is EXPSPACE-complete.

The coverability problem for Petri Nets is -complete.

The reachability problem for Petri nets was known to be -hard for a long time, but shown to be nonelementary, so probably not in. In 2022 it was shown to be Ackermann-complete.

Relationship to other classes
is known to be a strict superset of, , and. It is further suspected to be a strict superset of, however this is not known.

title: EXPSPACE