title: Gothic art

text: Gothic sculptures independent of architectural ornament were primarily created as devotional objects for the home or intended as donations for local churches, although small reliefs in ivory, bone and wood cover both religious and secular subjects, and were for church and domestic use. Such sculptures were the work of urban artisans, and the most typical subject for three dimensional small statues is the Virgin Mary alone or with child. Paris was the main centre of ivory workshops, and exported to most of northern Europe, though Italy also had a considerable production. An exemplar of these independent sculptures is among the collections of the Abbey Church of St Denis; the silver-gilt "Virgin and Child" dates to 1339 and features Mary enveloped in a flowing cloak holding an infantile Christ figure. Both the simplicity of the cloak and the youth of the child presage other sculptures found in northern Europe dating to the 14th century and early 15th century. Such sculpture shows an evolution from an earlier stiff and elongated style, still partly Romanesque, into a spatial and naturalistic feel in the late 12th and early 13th century. Other French Gothic sculptural subjects included figures and scenes from popular literature of the time. Imagery from the poetry of the troubadours was particularly popular among artisans of mirror-cases and small boxes presumably for use by women. The Casket with Scenes of Romances (Walters 71264) of 1330–50 is an unusually large example with space for a number of scenes from different literary sources.


title: Gothic art

text: Souvenirs of pilgrimages to shrines, such as clay or lead badges, medals and ampullae stamped with images were also popular and cheap. Their secular equivalent, the livery badge, showed signs of feudal and political loyalty or alliance that came to be regarded as a social menace in England under bastard feudalism. The cheaper forms were sometimes given away free, as with the 13,000 badges ordered in 1483 by King Richard III of England in fustian cloth with his emblem of a white boar for the investiture of his son Edward as Prince of Wales, a huge number given the population at the time. The Dunstable Swan Jewel, modelled fully in the round in enamelled gold, is a far more exclusive version, that would have been given to someone very close or important to the donor.


title: Buck Dharma

text: Donald Roeser (born November 12, 1947), known by his stage name Buck Dharma, is an American guitarist, singer, and songwriter. He is the sole constant member of hard rock band Blue Öyster Cult since the group's formation in 1967. He wrote and sang vocals on several of the band's best-known hits, including "(Don't Fear) The Reaper", "Godzilla" and "Burnin' for You".


title: Buck Dharma

text: Roeser was born in Queens, New York City. His father was an accomplished jazz saxophonist, and Roeser spent a lot of time listening to jazz music as a result. Because of this, Roeser developed an interest in the melodic arts at an early age, even playing the accordion for a brief time.


title: Buck Dharma

text: Roeser was influenced greatly by the British Invasion of 1964, and decided to pursue rock-and-roll music. He first started out playing the drums, but had to stop temporarily after breaking his wrist playing basketball. While recovering, Roeser learned to play guitar, and found he enjoyed it more than the drums.


title: Buck Dharma

text: During his high-school years at Smithtown Central High School, Roeser played guitar in various cover bands. At this time, he started to develop his own signature sound by imitating his favorite guitarists and combining their sounds with his own style. Roeser attended Clarkson University in New York, and joined a band that included later bandmate Albert Bouchard. The two played together on and off during the rest of their college career. At the end, both musicians abandoned potential degrees (Roeser's in Chemical Engineering), and decided to pursue music full-time. They moved into a band house near Stony Brook University, where Roeser was a part-time student, and started their careers.


title: Buck Dharma

text: Roeser and Albert Bouchard started the band Soft White Underbelly in 1967. Members included keyboardist Allen Lanier, singer Les Braunstein, bassist Andrew Winters and former music critic Sandy Pearlman (their producer). In 1968, they were signed by Elektra Records after the company's president Jac Holzman saw them perform. The band dropped Braunstein and added new singer Eric Bloom to their lineup - and recorded under the name Stalk-Forrest Group (after a bad gig forced them to change their name) in 1970. Elektra dropped the band because of problems with the personnel, and the album was shelved (it was eventually released in 2001 under the name "").


title: Buck Dharma

text: Roeser, along with Bouchard, Lanier, Pearlman, Bloom, and new member bassist Joe Bouchard (younger brother of Albert Bouchard) reformed with the name Blue Öyster Cult. They signed with Columbia Records in 1971, and released four albums between 1972 and 1975. By Blue Öyster Cult's fifth album "Agents of Fortune" in 1976, Roeser proved himself as a songwriter and vocalist with the band's signature song "(Don't Fear) The Reaper". As a result, Roeser's songwriting and vocals were more prevalent on the follow-up albums "Spectres", "Mirrors", "Cultosaurus Erectus" and "Fire of Unknown Origin". Most significantly, he penned and sang on the tracks "Godzilla" and "Burnin' for You".


title: Buck Dharma

text: In 1982, Roeser recorded and released "Flat Out", his first and only solo album to date. The tracks were all composed by Roeser (some co-written with Richard Meltzer, Neal Smith and Roeser's wife Sandy), with the exception of "Come Softly to Me", a song originally recorded by The Fleetwoods. The songs on the album were ones Roeser wanted to record with BÖC, but were perceived as too poppy by the other members of the band. Singles from the album were "Born to Rock" and "Your Loving Heart", both of which had music videos made but did not chart. The video for the former was part of an MTV promo along with Blotto's Metalhead clip, in which Buck made a cameo appearance, as well as playing guitar on the song.


title: Buck Dharma

text: Roeser and Blue Öyster Cult subsequently recorded several more albums that flopped commercially, but contained several of Roeser's compositions and many tracks with him on lead vocals. The band's commercial struggles, along with the loss of original members Albert Bouchard (1982) and Allen Lanier (1985), prompted Blue Öyster Cult to break up in mid 1986.


title: Buck Dharma

text: In 1985, Roeser and Bloom participated in Hear 'n Aid, a project created by Ronnie James Dio to raise money for famine relief in Africa. It included many famous heavy metal musicians. Hear n' Aid recorded the song "Stars", which includes a guitar solo by Roeser. Hear n' Aid also released a compilation album which included "Stars", as well as live outtakes from the participating artists.


title: Buck Dharma

text: In 1988 Blue Öyster Cult released "Imaginos", which was recorded between 1982 and 1988. The record was originally planned to be a concept album based on Sandy Pearlman's poetry by former drummer Albert Bouchard. At the insistence of Columbia Records, it was released under the band name. Despite largely positive reviews, the album did not do well commercially, and the band was dropped by Columbia. This was the last album featuring all original members, as the Bouchards left at the end of production.


title: Buck Dharma

text: In 1988, Roeser formed The Red and the Black with John Rogers on bass and Ron Riddle on drums. The band recorded demos, but was never signed by a record company and never released an album. As a result, the band split quickly. In 1989, Roeser contributed the instrumental "Gamera is Missing" to the album "Guitar's Practicing Musicians Volume 3" (later included on the CD re-release of "Flat Out").


title: Buck Dharma

text: After releasing "Imaginos", Roeser, Bloom and Lanier continued to tour as Blue Öyster Cult, with various musicians on bass and drums. In 1992, the band wrote the score for "Bad Channels" and composed two original songs for its soundtrack. In 1994, Blue Öyster Cult released "Cult Classic", an album containing remakes of their greatest hits.


title: Buck Dharma

text: In the late 1990s, Blue Öyster Cult signed with Sanctuary Records, and released two studio albums and one live album between 1998 and 2002. The band was dropped by the label in 2002. Roeser continues to tour extensively with the band, and in December 2012 reunited for a final time with all of the original members for the band's 40th Anniversary Concert.


title: Buck Dharma

text: On January 1, 2015, Roeser released "Fight", an original song, on his SoundCloud account. It is his first newly released material since 2001. The song was later re-recorded with Blue Öyster Cult, appearing on their fifteenth album "The Symbol Remains" (2020).


title: Buck Dharma

text: Roeser appears on the song "Metal Head" by the comedy-rock group Blotto and appears in the song's video, watching television.


title: Buck Dharma

text: In 2002, Roeser and his wife created "The Dharmas", a web-series exclusively featured on Roeser's website. The web-series is a comical, fictionalized insight on the life and times of the Roeser family.


title: Buck Dharma

text: In 1996, Roeser heard about Ricky Browning, a 10-year-old fan of Roeser's "Godzilla" who was battling a brain tumor. Roeser organized a benefit concert to help with the family's medical costs. Roeser, his wife Sandy, drummer John Miceli and bassist Danny Miranda played the concert under the name "Buck Dharma Band". Roeser taped the concert and released a video of it, which includes the story of Browning. Browning eventually succumbed to his illness. The Roesers still have a close relationship with the Browning family.


title: Buck Dharma

text: One of his Steinberger guitars has a custom body made to look like Swiss cheese; Dharma calls this guitar his "Cheeseberger".


title: Buck Dharma

text: His other equipment use includes: a "Giuliano Balestra Vulcan", a Fender Stratocaster, a "St. Blues" and custom models built by "Rick Kresiak", "Harper Guitars" and "Warren Guitars". Many of his guitars were made by White Plains-based custom guitar maker, Giuliano.


title: Buck Dharma

text: Roeser got the stage name "Buck Dharma" in the late 1960s. Manager Sandy Pearlman came up with the idea of creating eccentric stage names for Blue Öyster Cult's members. Every member rejected their new stage name except for Roeser, who liked the name and the idea of having an alternate persona.


title: Sony Entertainment

text: Sony Entertainment, Inc. is an American entertainment company established in 2012. It focuses on most of Sony's motion picture, television and music businesses. It is a subsidiary of the Japanese Sony Group Corporation, managed by Sony's American subsidiary, Sony Corporation of America.


title: Sony Entertainment

text: On March 30, 2012, Michael Lynton, co-chairman and CEO of Sony Pictures Entertainment (SPE), was named as CEO of Sony Corporation of America to oversee all of Sony's global entertainment businesses and Nicole Seligman, Executive Vice President and General Counsel of Sony Corporation, was named as president. On April 9, 2013, Lynton renewed his contract with the company.


title: Sony Entertainment

text: On February 18, 2016, Seligman resigned after 15 years working for Sony and remained with the company until the end of March.


title: Sony Entertainment

text: On January 13, 2017, Lynton announced that he was stepping down as CEO of Sony Entertainment and chairman and CEO of Sony Pictures Entertainment to be chairman for Snap Inc. He was later replaced by Anthony Vinciquerra on June 1, 2017 after he was named as chairman/CEO of SPE.


title: Sony Entertainment

text: It was reported in December 2016 by multiple news outlets that Sony was considering restructuring its U.S. operations by merging its TV & film business, Sony Pictures Entertainment, with its gaming business, Sony Interactive Entertainment. According to the reports, such a restructuring would have placed Sony Pictures under Sony Interactive's CEO, Andrew House, though House wouldn't have taken over day-to-day operations of the film studio. According to one report, Sony was set to make a final decision on the possibility of the merger of the TV, film, & gaming businesses by the end of its fiscal year in March of the following year (2017). However, judging by Sony's activity in 2017, the rumored merger never materialized.


title: Sony Entertainment

text: On July 17, 2019, Sony announced that they will merge Sony Music Entertainment and Sony/ATV Music Publishing to form the Sony Music Group. The merger was finalized on August 1, 2019.


title: In the Name of the King

text: In the Name of the King: A Dungeon Siege Tale, or simply In the Name of the King, is a 2007 action-fantasy film directed by Uwe Boll and starring Jason Statham, Claire Forlani, Leelee Sobieski, John Rhys-Davies, Ron Perlman and Ray Liotta. It is inspired by the "Dungeon Siege" video game series. The English-language film was an international (German, American, and Canadian) co-production and filmed in Canada. It premiered at the Brussels Festival of Fantastic Films in April 2007 and was released in theatres in November 2007.


title: In the Name of the King

text: Upon its release, the film was a major critical and commercial failure, receiving overwhelmingly negative reviews from critics and grossing $13.1 million against a budget of $60 million.


title: In the Name of the King

text: In the kingdom of Ehb, a man known only as Farmer is living a happy life with his wife, Solana, and their young son, Zeph, in the town of Stonebridge. One day, the town gets attacked by the Krug, creatures known to be primitive and animal-like. They surprise the people by taking up arms, donning armour and are fighting with courage, intelligence and ferocity. It is all because they are magically controlled by Gallian, a powerful Magus who has become sadistic and megalomaniacal, and seeks to conquer and rule Ehb. During the attack, Farmer, along with his friend, Norick and his brother-in-law, Bastian, fights off the Krug. He fails to save Zeph; who is killed by Gallian via a Krug avatar. Through a Krug, Gallian claims to be unable to read Farmer. Solana and other Stonebridge inhabitants are taken prisoner.


title: In the Name of the King

text: King Konreid, Commander Tarish and Ehb's soldiers arrive at Stonebridge to survey the damage and recruit others to join their army. Merick, another Magus who serves Konreid, tries to learn of Farmer's identity when he notices Norick, who he believes he has seen before. Farmer, Norick and Bastian set off on their own to find Solana. Meanwhile, Merick's daughter, Muriella, who fell in love with Gallian, ends her romance with him after seeing his dark nature and realizing that he only trained her power so he can take it away. She confesses to her father, who believes that her love for Gallian has created an imbalance of their powers in Gallian's favour. Meanwhile, Konreid's selfish and immature nephew, Duke Fallow is in league with Gallian and he seeks to take his uncle's place. He attempts to poison Konreid and takes a company of Ehb soldiers for his own. Soon after, Konreid heals and leads his army to go and fight Gallian's forces.


title: In the Name of the King

text: Going through Sedgwick Forest, Farmer and his companions encounter the reclusive nymphs led by Elora, who leads them out of the forest. When they attempt to rescue Solana from the Krug, Farmer gets knocked out, and Norick and Bastian get captured. While Farmer is being hanged by another one of Gallian's avatars, he kills the avatar, frees himself and is rescued by Merick. Farmer is taken to Konreid and his army's camp, where Merick reveals that Farmer is Konreid's long lost son and his real name is Camden Konreid. He explains that many years ago, a young Farmer was present during a battle at a place known as Oxley Pass, where he was found by Norick. Norick was considered to be the adoptive father, but Farmer was cared for by Stonebridge's inhabitants and was kept safe from all the chaos that ravaged Ehb. Konreid and Farmer both disapprove of Merick's claims.


title: In the Name of the King

text: Konreid catches Fallow, in his treachery, which leaves Fallow only his personal guard as the company turns from him and joins the rest of the army. Soon after, a battle erupts between Ehb's army and the Krug. Ehb's army, along with Farmer, eventually gain the upper hand and force the Krug to retreat, but Fallow succeeds in mortally wounding Konreid. After the battle, Konreid and Farmer learn that they both share similar knowledge as Konreid declares Farmer his son with his last breath and dies. Meanwhile, Tarish challenges Fallow to a duel. Tarish wins and Fallow is taken away. Farmer, who is now the new king, readies everybody for the next battle.


title: In the Name of the King

text: Meanwhile, Norick, Bastian and Solana are taken to Gallian's lair at Christwind Hold. Norick is killed while he and Bastian fight the Krug. Solana is taken to Gallian, who can sense Farmer within her, who reveals that Solana is pregnant with Farmer's second child. Going on a mission to infiltrate Gallian's lair, Farmer is joined by Merick, Muriella and Elora, who has sided with Ehb against Gallian, while Tarish and the remaining army hold off against the advancing Krug. Merick magically enters the lair and fights Gallian, who manages to kill Merick. Farmer and Muriella manage to go into the lair as well, but Elora stays behind.


title: In the Name of the King

text: Farmer finds Solana and fights Gallian in a sword battle. When Gallian resorts to using his magic to gain the upper hand, he prepares to kill him until Solana stabs him in the back. Muriella arrives and tries to save Farmer but Gallian defeats Muriella by weakening her magic. With him wounded, Farmer quickly defeats Gallian by slitting his throat and killing him. Gallian's magic influence goes away and the Krug go back to being primitive, saving Bastian and the prisoners, and Tarish and his battered forces. Having finally avenged his son, Farmer and Solana are happily reunited as the kingdom is saved.


title: In the Name of the King

text: Boll has said that two versions will be produced due to length. The first will run for 127 minutes as a single movie trimmed down for cinematic release. The second, a director's cut, was made for a DVD release and ran 155 minutes.


title: In the Name of the King

text: The film was shot near the Municipality of Sooke, the westernmost area of the Greater Victoria, Capital Regional District (CRD), British Columbia. Locals and First Nations people were recruited as extras and for other duties.


title: In the Name of the King

text: Visual effects were added in post-production. Companies included Elektrofilm, Frantic Films, The Orphanage, PICTORION das werk, Rocket Science VFX, Technicolor Creative Services, TVT postproduction, and upstart! Animation.


title: In the Name of the King

text: The German power metal band Blind Guardian recorded the movie's main theme, "Skalds and Shadows". The British progressive metal band Threshold contributed the song "Pilot in the Sky of Dreams" from their album "Dead Reckoning". The Swedish power metal band, HammerFall, also contributed a track, "The Fire Burns Forever". Wolfgang Herold was the executive soundtrack producer.


title: In the Name of the King

text: "In the Name of the King" was a box office bomb, grossing $2.98 million in its United States opening, not cracking that week's top ten. It had grossed $10.3 million worldwide, including $2.47 million in Germany, $1.39 million in Russia and $1.22 million in Spain. Afterwards, Uwe Boll announced that this would be his first and last movie with a large budget.


title: In the Name of the King

text: The film received extremely negative reviews from critics. The film holds approval rating on the review aggregator website Rotten Tomatoes, based on reviews, with an average rating of . The website's critics consensus reads: "Featuring mostly wooden performances, laughable dialogue, and shoddy production values, "In the Name of the King" fulfills all expectations of an Uwe Boll film." The film is also ranked in that site's 100 worst reviewed films of the 2000s and in 2008, "Time" listed the film on their list of top ten worst video games movies. Metacritic reported the film had an average score of 15 out of 100, based on 11 reviews — indicating "overwhelming dislike."


title: In the Name of the King

text: Many critics have attacked the film's close resemblances to other fantasy films, especially the popular "Lord of the Rings" films.


title: In the Name of the King

text: The film was nominated for five Razzie Awards, including Worst Picture, Worst Screenplay, Worst Supporting Actor (Burt Reynolds) and Worst Supporting Actress (Leelee Sobieski), with Uwe Boll winning Worst Director.


title: In the Name of the King

text: Despite being considered a bomb, Boll filmed a sequel titled "". Filming began on December 1, 2010, and it was released in 2011. The film stars Dolph Lundgren and Natassia Malthe.


title: In the Name of the King

text: A third film, "", was filmed in 2013 but not released until 2014. The film starred Dominic Purcell, with Boll returning to direct.


title: In the Name of the King

text: The DVD, released on April 15, 2008, does not include the 156-minute version. The Blu-ray release in December 2008 contains this edition. 813,147 units were sold, gathering a revenue of $14,865,984, more than its box office grossing.


title: Computational complexity theory

text: In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.


title: Computational complexity theory

text: A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.


title: Computational complexity theory

text: Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.


title: Computational complexity theory

text: A computational problem can be viewed as an infinite collection of "instances" together with a set (possibly empty) of "solutions" for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the "instance" is a particular input to the problem, and the "solution" is the output corresponding to the given input.


title: Computational complexity theory

text: To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.


title: Computational complexity theory

text: When considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are bitstrings. As in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary.


title: Computational complexity theory

text: Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.


title: Computational complexity theory

text: Decision problems are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either "yes" or "no", or alternately either 1 or 0. A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an algorithm, whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer "yes", the algorithm is said to accept the input string, otherwise it is said to reject the input.


title: Computational complexity theory

text: An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.


title: Computational complexity theory

text: A function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the traveling salesman problem and the integer factorization problem.


title: Computational complexity theory

text: It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples ("a", "b", "c") such that the relation "a" × "b" = "c" holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.


title: Computational complexity theory

text: To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2"n" vertices compared to the time taken for a graph with "n" vertices?


title: Computational complexity theory

text: If the input size is "n", the time taken can be expressed as a function of "n". Since the time taken on different inputs of the same size can be different, the worst-case time complexity T("n") is defined to be the maximum time taken over all inputs of size "n". If T("n") is a polynomial in "n", then the algorithm is said to be a polynomial time algorithm. Cobham's thesis argues that a problem can be solved with a feasible amount of resources if it admits a polynomial-time algorithm.


title: Computational complexity theory

text: A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata, lambda calculus or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.


title: Computational complexity theory

text: Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.


title: Computational complexity theory

text: A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.


title: Computational complexity theory

text: Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random-access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.


title: Computational complexity theory

text: However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that non-deterministic time is a very important resource in analyzing computational problems.


title: Computational complexity theory

text: For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The "time required" by a deterministic Turing machine "M" on input "x" is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine "M" is said to operate within time "f"("n") if the time required by "M" on each input of length "n" is at most "f"("n"). A decision problem "A" can be solved in time "f"("n") if there exists a Turing machine operating in time "f"("n") that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time "f"("n") on a deterministic Turing machine is then denoted by DTIME("f"("n")).


title: Computational complexity theory

text: Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.


title: Computational complexity theory

text: The best, worst and average case complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size "n" may be faster to solve than others, we define the following complexities:


title: Computational complexity theory

text: The order from cheap to costly is: Best, average (of discrete uniform distribution), amortized, worst.


title: Computational complexity theory

text: For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O("n"). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O("n" log "n"). The best case occurs when each pivoting divides the list in half, also needing O("n" log "n") time.


title: Computational complexity theory

text: To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound "T"("n") on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most "T"("n"). However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of "T"("n") for a problem requires showing that no algorithm can have time complexity lower than "T"("n").


title: Computational complexity theory

text: Upper and lower bounds are usually stated using the big O notation, which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if "T"("n") = 7"n" + 15"n" + 40, in big O notation one would write "T"("n") = O("n").


title: Computational complexity theory

text: A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the following factors:


title: Computational complexity theory

text: Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following:


title: Computational complexity theory

text: But bounding the computation time above by some concrete function "f"("n") often yields complexity classes that depend on the chosen machine model. For instance, the language {"xx" | "x" is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" . This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.


title: Computational complexity theory

text: Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:


title: Computational complexity theory

text: The logarithmic-space classes (necessarily) do not take into account the space needed to represent the problem.


title: Computational complexity theory

text: Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using Boolean circuits; and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.


title: Computational complexity theory

text: For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME("n") is contained in DTIME("n"), it would be interesting to know if the inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved.


title: Computational complexity theory

text: The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.


title: Computational complexity theory

text: Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at most as difficult as another problem. For instance, if a problem "X" can be solved using an algorithm for "Y", "X" is no more difficult than "Y", and we say that "X" "reduces" to "Y". There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions.


title: Computational complexity theory

text: The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.


title: Computational complexity theory

text: This motivates the concept of a problem being hard for a complexity class. A problem "X" is "hard" for a class of problems "C" if every problem in "C" can be reduced to "X". Thus no problem in "C" is harder than "X", since an algorithm for "X" allows us to solve any problem in "C". The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP is the set of NP-hard problems.


title: Computational complexity theory

text: If a problem "X" is in "C" and hard for "C", then "X" is said to be "complete" for "C". This means that "X" is the hardest problem in "C". (Since many problems could be equally hard, one might say that "X" is one of the hardest problems in "C".) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem P = NP is not solved, being able to reduce a known NP-complete problem, Π, to another problem, Π, would indicate that there is no known polynomial-time solution for Π. This is because a polynomial-time solution to Π would yield a polynomial-time solution to Π. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.


title: Computational complexity theory

text: The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis. The complexity class NP, on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.


title: Computational complexity theory

text: The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution. If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of integer programming problems in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems. The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute. There is a US$1,000,000 prize for resolving the problem.


title: Computational complexity theory

text: It was shown by Ladner that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete. Such problems are called NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.


title: Computational complexity theory

text: The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai and Eugene Luks has run time formula_3 for graphs with "n" vertices, although some recent work by Babai offers some potentially new perspectives on this.


title: Computational complexity theory

text: The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than "k". No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time formula_4 to factor an odd integer "n". However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.


title: Computational complexity theory

text: Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ NP ⊆ PP ⊆ PSPACE, but it is possible that P = PSPACE. If P is not equal to NP, then P is not equal to PSPACE either. Since there are many known complexity classes between P and PSPACE, such as RP, BPP, PP, BQP, MA, PH, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.


title: Computational complexity theory

text: Along the same lines, co-NP is the class containing the complement problems (i.e. problems with the "yes"/"no" answers reversed) of NP problems. It is believed that NP is not equal to co-NP; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then P is not equal to NP, since P=co-P. Thus if P=NP we would have co-P=co-NP whence NP=P=co-P=co-NP.


title: Computational complexity theory

text: Similarly, it is not known if L (the set of all problems that can be solved in logarithmic space) is strictly contained in P or equal to P. Again, there are many complexity classes between the two, such as NL and NC, and it is not known if they are distinct or equal classes.


title: Computational complexity theory

text: A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice "any" solution takes too many resources to be useful, is known as an '. Conversely, a problem that can be solved in practice is called a ', literally "a problem that can be handled". The term "infeasible" (literally "cannot be done") is sometimes used interchangeably with "intractable", though this risks confusion with a feasible solution in mathematical optimization.


title: Computational complexity theory

text: Tractable problems are frequently identified with problems that have polynomial-time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If NP is not the same as P, then NP-hard problems are also intractable in this sense.


title: Computational complexity theory

text: However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.


title: Computational complexity theory

text: To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2 operations before halting. For small "n", say 100, and assuming for the sake of example that the computer does 10 operations each second, the program would run for about 4 × 10 years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001 operations is practical until "n" gets relatively large.


title: Computational complexity theory

text: Similarly, a polynomial time algorithm is not always practical. If its running time is, say, "n", it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even "n" or "n" algorithms are often impractical on realistic sizes of problems.


title: Computational complexity theory

text: Continuous complexity theory can refer to complexity theory of problems that involve continuous functions that are approximated by discretizations, as studied in numerical analysis. One approach to complexity theory of numerical analysis is information based complexity.


title: Computational complexity theory

text: Continuous complexity theory can also refer to complexity theory of the use of analog computation, which uses continuous dynamical systems and differential equations. Control theory can be considered a form of computation and differential equations are used in the modelling of continuous-time and hybrid discrete-continuous-time systems.


title: Computational complexity theory

text: An early example of algorithm complexity analysis is the running time analysis of the Euclidean algorithm done by Gabriel Lamé in 1844.


title: Computational complexity theory

text: Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.


title: Computational complexity theory

text: The beginning of systematic studies in computational complexity is attributed to the seminal 1965 paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard E. Stearns, which laid out the definitions of time complexity and space complexity, and proved the hierarchy theorems. In addition, in 1965 Edmonds suggested to consider a "good" algorithm to be one with running time bounded by a polynomial of the input size.


title: Computational complexity theory

text: Earlier papers studying problems solvable by Turing machines with specific bounded resources include John Myhill's definition of linear bounded automata (Myhill 1960), Raymond Smullyan's study of rudimentary sets (1961), as well as Hisao Yamada's paper on real-time computations (1962). Somewhat earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity measure. As he remembers:


title: Computational complexity theory

text: In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.


title: Tom Johnston (musician)

text: Charles Thomas Johnston (born August 15, 1948) is an American musician. He is a guitarist and vocalist, known principally as a founder, guitarist, lead vocalist and songwriter for the rock group the Doobie Brothers, as well as for his own solo career. He has played off and on with the Doobie Brothers for 50 years, in several styles. He was inducted into the Rock and Roll Hall of Fame as a member of the Doobie Brothers in 2020.


title: Tom Johnston (musician)

text: Johnston is most well known for both his lead guitar and vocal role in the Doobie Brothers, as well as for his adaptation of his own acoustic guitar style, blending a unique strum and percussive accented rhythm at the same time on one instrument. This style, interwoven with melodic hammer-ons, gave Johnston an early signature sound in popular 1970s rock music. All the rhythm structures behind "Long Train Runnin'" and "Listen to the Music" were formulated first for an acoustic guitar, and then re-applied in similar style on an electric guitar.


title: Tom Johnston (musician)

text: Johnston was born in Visalia, California. His greatest musical influences during his youth included Little Richard, Bo Diddley, Elvis Presley, James Brown, and other rhythm and blues artists featured on the radio in the 1950s. After brief school stints with the saxophone and clarinet, at the age of twelve Johnston took up guitar. He said, "I started out [on] the clarinet at seven, and I played that for eight years. I also played the saxophone for three years, drums for a year and a half, and took up the guitar when I was in the seventh grade. That was pretty much of a rebellion/image trip. But I felt at home on the guitar. I loved the saxophone and played tenor and baritone. But unfortunately, when I hung the clarinet up, I hung up all the reed instruments and just started playing guitar, and I never touched them again. I taught myself guitar and a little piano at home. I played piano on the first album "The Doobie Brothers", and a little harmonica on a few others." In his early career he played in a variety of bands, including a Mexican wedding band that played half soul and half Latin music. His interest in rhythm and blues led to his singing in a soul group from a neighboring town and, eventually, his own blues band.


title: Tom Johnston (musician)

text: Johnston moved to San Jose to finish college and started playing in bands around town. It was there that he met Skip Spence, a former drummer with Jefferson Airplane, and guitarist/founding member of a group that had a major influence on the Doobie Brothers – Moby Grape. Spence introduced Johnston to John Hartman. Johnston was a graphic design art major at San José State University and wound up living at 285 South 12th Street, which was a musical center for San Jose at the time. "It didn't matter if they played B-3 or drums, guitar, bass, or horns, they all ended up in our basement," Johnston recalls. Johnston and Hartman soon formed their own band, Pud, featuring Greg Murphy on bass. Pud played many clubs in and around San Jose, including the Golden Horn Lounge (which no longer exists) in Cupertino, California. Here they met Pat Simmons. Hartman and Johnston lived in the 12th Street house for about four years; whereupon Dave Shogren joined them to replace Greg Murphy and Pat Simmons was recruited, they had the nucleus of a new band, and Pud gave way to the Doobie Brothers.


title: Tom Johnston (musician)

text: Throughout much of an initial seven-year and six-album discography, Johnston wrote and sang many of the Doobie Brothers' early hits, including "Listen to the Music" (#11 Top 100 Billboard Hit −1972), "Rockin' Down the Highway," "China Grove" (#15 Billboard Hot 100 Hit), "Long Train Runnin'" (#8 Billboard Hot 100 Hit), "Another Park, Another Sunday" (#32 Billboard Hot 100 Hit), and "Eyes of Silver" (#52 Billboard Hot 100 Hit). He also sang the hit song "Take Me in Your Arms" (#11 Billboard Hot 100 Hit −1975) (written by Holland-Dozier-Holland).


title: Tom Johnston (musician)

text: In December 1973, the British music magazine "NME" reported the relatively trivial news that Johnston had been arrested in California on a charge of marijuana possession. More seriously however, following years of a road touring lifestyle and health issues surrounding stomach ulcers which stood as a challenge since high school, Johnston became severely ill on the eve of a major tour beginning in Memphis, Tennessee in 1975 to promote "Stampede". Johnston's condition was so precarious that he required emergency hospitalization for a bleeding ulcer. With Johnston convalescing and the tour already underway, fellow Doobie Brother Jeff Baxter proposed recruiting a fellow Steely Dan alum to fill the hole. This led to the emergency hiring of Michael McDonald, who became the lead singer of the band. Restored to fitness in 1976 and briefly back in the band, Johnston contributed one original song to "Takin' It to the Streets" ("Turn It Loose"), and also added a vocal cameo to Pat Simmons' tune "Wheels of Fortune". He also made live appearances with the band in 1976 (appearing in a concert filmed that year at Winterland in San Francisco, excerpts from which appear occasionally on VH1 Classic), but was sidelined once again in the fall due to exhaustion. None of Johnston's songs appeared on "Livin' on the Fault Line", though he had written and the band had recorded five of his compositions for the album. Finally, before "Fault Line" was released, Johnston had his songs removed and left the band that he co-founded (though he received credit for guitars and vocals and was pictured on the album's inner sleeve band photo). After a few years of restored health but growing differences in musical direction between band members, Johnston finally left the band in 1977 to pursue a solo career that produced two albums with Warner Bros: "Everything You've Heard Is True" and "Still Feels Good" (reissued on compact disc by Wounded Bird Records), and Billboard Hot 100 hit "Savannah Nights" (#34 Top 100 Billboard Hit −1980).


title: Tom Johnston (musician)

text: Johnston toured in the late 1970s and early 1980s with the Tom Johnston Band, which featured fellow Doobie John Hartman on drums. While working on his solo projects, in 1982 Johnston rejoined the band for a farewell tour concert, after which the Doobie Brothers ceased performing as a band for the next five years.


title: Tom Johnston (musician)

text: In 1985, Johnston toured US clubs with a group called Border Patrol, that also included former Doobies Michael Hossack and briefly Patrick Simmons. This group toured but never recorded. In 1987, he contributed a tune to the "Dirty Dancing" soundtrack entitled "Where Are You Tonight?"


title: Tom Johnston (musician)

text: Johnston joined the Doobie Brothers when they reunited for a brief tour in 1987. This event led to the permanent reformation of the band, with Johnston again performing alongside co-founder Simmons. With Simmons, Johnston wrote "Long Train Runnin': Our Story of the Doobie Brothers" (2022).


title: Tom Johnston (musician)

text: "Mine [first guitar] was an arch-back Harmony acoustic with f-holes. After that I got a Kay single-pickup electric with a cheap amplifier as that's all I could afford. Johnston now owns a mid-50s Fender Stratocaster that has been in his collection since the 1970s. He has a 1970 Les Paul Deluxe goldtop with classic white P-90 'soapbar' pickups affixed with an American Flag, that has been his primary Les Paul for 40 years. He also relies upon a 2008 PRS Custom 24 as a touring backup for his primary PRS. His primary touring guitar is a 2009 PRS 25th Anniversary Custom 24. It has a Modern Eagle inlay on the headstock and 57/08 pickups. "I've got a lot of guitars. Basically, everything I use on the road is PRS and that is what I play live. I use two basic guitars live that I trade off and I have a Martin acoustic that I play as well live. It is pretty much all about Paul Reed Smith right now. At home I have a Stratocaster and I have some older guitars I have had for a long time, an old Les Paul, an old 335, a couple Strats and a Telecaster. But live and when I am out on the road, it is strictly PRS."


title: Tom Johnston (musician)

text: While primarily an electric guitarist, Johnston also plays acoustic guitars for exploration and song writing. He started with a Gibson J-50 which was used to record all acoustic guitar parts on the first four Doobie Brother albums and after it was stolen moved to Martin guitars. In his personal collection are a 1962 Martin 00–18 and a 1975 Martin D-42, and he has written various songs on the 00-18. Johnston uses a variety of software in his home studio for writing, and Digital Performer by MOTU as his recording software program.


title: Tom Johnston (musician)

text: Johnston has employed traditionally a three finger Clapton-Hendrix lead fingerstyle, only using all four fingers for barre chords. He said, "I use my little finger to play chords, but not for playing solos. The direction in which I bend a string depends on where the string I'm bending is on the neck. The lower strings are going to be pulled down, and the high strings are going to be pushed up. I use a lot of vibrato when I play solo. And for picking, it has to be up and down if you want to do a lot of speed. It's also better for clarity. Anything faster than quarter notes, you either have to use alternating picking or play with a regular flatpick and fingers."


title: Tom Johnston (musician)

text: Johnston has traditionally employed Herco Nylon Flex 50 flatpicks (old "Herco mediums"), allowing for the right combination of flex and durability for his chukka-style rhythm. He said "I always use Herco medium because they don't break, and they take forever to wear out. Actually the worst thing you can do with a Herco is lose it. They are easy to hold on to as well and I do sweat a lot playing live. In fact, I usually eat the nickel off the strings right down to the brass (circa 1976)."


title: Tom Johnston (musician)

text: In 2007 C.F. Martin & Co. released a limited run of 35 Tom Johnston Signature Edition Doobie-42 Artist Edition guitars, and Elderly Music Tom Johnston Doobie 42.


title: Tom Johnston (musician)

text: Johnston and his wife Diane now live in northern Marin County, California. His daughter Lara Johnston is a singer-songwriter. She has toured both as a solo act opening for the bands KISS and Heart, and as a backing vocalist for Don Henley and Belinda Carlisle. She was a competitor on MTV's "Rock the Cradle" and was a 2011 participant in "American Idol". Tom Johnston's son Christopher lives and works in Marin.


title: Badmotorfinger

text: Badmotorfinger is the third studio album by American rock band Soundgarden, released on October 8, 1991, through A&M Records. Soundgarden began the recording sessions for the album with new bassist Ben Shepherd in the spring of 1991. The album maintained the band's heavy metal sound, while featuring an increased focus on songwriting compared to the band's previous releases. AllMusic considered the album's music to be "surprisingly cerebral and arty"; alternative tunings and odd time signatures were present on several of the album's songs, and lyrics were intended to be ambiguous and evocative.


title: Badmotorfinger

text: The focus on the Seattle grunge scene helped bring attention to "Badmotorfinger", and the singles "Outshined" and "Rusty Cage" were able to find a major audience in rock radio and MTV. "Badmotorfinger" became the band's highest charting album at the time on the "Billboard" 200, where it peaked at number 39. The album received critical acclaim, citing the significant improvements over earlier releases and evolution in the band's sound. Soundgarden supported the album with tours of North America and Europe, including opening for Guns N' Roses on the Use Your Illusion Tour. In 1992, "Badmotorfinger" was nominated for the Grammy Award for Best Metal Performance, and it was certified double platinum by the Recording Industry Association of America in 1996.


title: Badmotorfinger

text: "Badmotorfinger" has been classified by various critics as grunge, alternative metal, heavy metal and hard rock. Steve Huey of AllMusic said the songwriting on the album "takes a quantum leap in focus and consistency", adding: "It's surprisingly cerebral and arty music for a band courting mainstream metal audiences, but it attacks with scientific precision." Guitarist Kim Thayil jokingly called it the "Heavy Metal "White Album"". Frontman Chris Cornell said, "I think there's songs on the new record which are almost more commercially viable because they have that memorable feel to them, and I think if anyone expected us to come out and make something more commercial than "Louder Than Love" [the band's previous album], then I'm glad that they were surprised." He added that the album was more representative of how the band was live.


title: Badmotorfinger

text: Compared with "Louder Than Love", the band took a more collaborative approach to the writing process for "Badmotorfinger". It was Soundgarden's first album with bassist Ben Shepherd, who replaced Jason Everman in April 1990, and Cornell said Shepherd brought a "fresh and creative" approach to the recording sessions, while the band as a whole said his knowledge of music and writing skills redefined the group. Before joining, Soundgarden had been Shepherd's favorite band. Shepherd contributed the song "Somewhere" and collaborated on the musical composition of several other songs on the album, as did Thayil and drummer Matt Cameron. Thayil said Shepherd's contributions helped make the album "faster" and "weirder".


title: Badmotorfinger

text: Several of the album's songs utilize alternative tunings, such as "Rusty Cage", "Searching with My Good Eye Closed", and "Holy Water" (on all of which the bottom E string of the guitars is tuned down to B), and "Mind Riot" (on which every string is tuned to one of several octaves of E). There are also some unusual time signatures on the album, with Thayil quoted as saying he didn't "push for weird time signatures", but rather "push[ed] to get the quirkiness out of things".


title: Badmotorfinger

text: Regarding the lyrics, Cornell said he tried to not get too specific and was more interested in letting ambiguity "[create] colourful images." Thayil compared listening to the album to "reading a novel [about] man's conflict with himself and society, or the government, or his family, or the economy, or anything." Cornell said "Outshined" is about going from "periods of extreme self-confidence" to "plummeting in the opposite direction". "Jesus Christ Pose" was written about famous people who exploit the symbol of Jesus' crucifixion to suggest they're persecuted by the public. Thayil wrote the lyrics for "Room a Thousand Years Wide", and said the song is about "experience in general". "Holy Water" was written about people who force their beliefs onto others. "New Damage" subtly criticizes the right-wing government of the United States.


title: Badmotorfinger

text: The album was recorded in the spring of 1991 at Studio D in Sausalito, California, Bear Creek Studios in Woodinville, Washington, and A&M Studios in Los Angeles, California. Soundgarden chose to work with producer Terry Date, as it had on "Louder Than Love", because, according to Cornell, the band had a good relationship with Date and did not want to go through the pressure of trying to find a new producer. One example of the innovative techniques used to record the album is that, for the opening song, "Rusty Cage", Thayil used a wah pedal as an audio filter, which resulted in an unusual guitar sound he said produced a guitar riff that "almost sounds backward".


title: Badmotorfinger

text: The "Badmotorfinger" logo on the cover of the album was drawn by guitarist Mark Dancey of the Sub Pop band Big Chief and consists of a jagged, cyclone-like design, in the center of which is a triangle that has the album's title along the interior perimeter and a spark plug in the middle. Thayil suggested the title "Badmotorfinger" as a joke on the Montrose song "Bad Motor Scooter" and said, regarding the title: "It was sort of off the top of my head. I simply like it because it was colorful. It was kinda aggressive, too ... It conjures up a lot of different kinds of images. We like the ambiguity in it, the way it sounded and the way it looked."


title: Badmotorfinger

text: "Badmotorfinger" was scheduled for release on September 24, 1991, but A&M Records pushed it back to October 8 due to "production problems." Coming a month and a half after Pearl Jam's "Ten" and just weeks after Nirvana's "Nevermind" and Red Hot Chili Peppers’ "Blood Sugar Sex Magik" (both of which were released on September 24), it has been credited with helping to break alternative rock and grunge into the mainstream. Although overshadowed at the time of its release by the sudden popularity of "Nevermind", the attention that album brought to the Seattle music scene helped Soundgarden get broader exposure, and "Badmotorfinger" peaked at number 39 on the "Billboard" 200 album chart on February 29, 1992. It was among the 100 top selling albums of 1992, sold a million copies in the early 1990s, and was certified platinum by the RIAA in January 1993; it was certified double platinum, signifying two million shipped copies, in April 1996.


title: Badmotorfinger

text: The album included the singles "Jesus Christ Pose", "Outshined", and "Rusty Cage", which gained considerable airtime on alternative rock radio stations. The music videos for "Outshined" and "Rusty Cage" gained considerable airtime on MTV, but the video for "Jesus Christ Pose", the album's lead single, was removed from MTV's playlist amidst widespread controversy over the perceived anti-Christian message of the song and video. Promotion of the song also precipitated death threats against the band while they were on tour to support the album in the United Kingdom.


title: Badmotorfinger

text: In a contemporary review for "Spin", Lauren Spencer hailed "Badmotorfinger" as a "garden of sound" that drew on older hard rock influences without sounding "derivative". Ann Powers of "Blender" said: "Cornell strikes the perfect Jesus Christ pose on this sonic wallop", while "Entertainment Weekly" critic Gina Arnold commended Soundgarden for writing more engagingly than their contemporaries, "who seldom get beyond extolling booze, girls, and cars". She concluded in her review that the record was more "stylishly bombastic rather than bludgeoningly bombastic. Tuneless heavy metal is, after all, still tuneless heavy metal, and in that department, Soundgarden are as functional as they make 'em." In a retrospective review, AllMusic staff-writer Steve Huey deemed the album "heavy, challenging hard rock full of intellectual sensibility and complex band interplay." Robert Christgau was less enthusiastic, finding it "credible" as a metal record because of Thayil's impressive use of guitar noise, but less impressive lyrically, writing: "Chris Cornell howls on about 'lookin for the paradigm' and 'your Jesus Christ pose' (I swear, that's the good stuff)".


title: Badmotorfinger

text: At the 1992 Grammy Awards, "Badmotorfinger" received a nomination for Best Metal Performance. That same year, the album won a Northwest Area Music Award for Best Metal Album. It was ranked number 45 in the October 2006 issue of "Guitar World" on the magazine's list of the 100 greatest guitar albums of all time and, in April 2019, was ranked number 2 on Rolling Stone's "50 Greatest Grunge Albums" list.


title: Badmotorfinger

text: Buzz Osborne, whose band Melvins had a massive influence on grunge, called "Badmotorfinger" his favorite grunge album of all time, praising its sophistication and complex structures. In 2010, singer Greg Puciato named "Room a Thousand Years Wide" his favorite song.


title: Badmotorfinger

text: A 2-LP gatefold of the album was also made available, with a limited edition of 1,000 produced using silver-colored vinyl.


title: Badmotorfinger

text: The "Badmotorfinger" reissue was created using a backup digital audio tape safety copy of the album, as the original master tapes were damaged or destroyed in the 2008 Universal Studios fire, which affected the label group's tape vault and purportedly destroyed material from hundreds of other recording artists. According to a document filed as part of a class action lawsuit Soundgarden and other artists brought against UMG as a result of the fire, the label made the band aware in May 2015 that the original half-inch master tape of "Badmotorfinger" had been destroyed and was unavailable for use on the remaster project.


title: Badmotorfinger

text: Following the release of "Badmotorfinger", Soundgarden went on a tour in North America during October and November 1991. Following this tour, they were selected by Guns N' Roses for an opening slot on that band's Use Your Illusion Tour. After this, Soundgarden took a slot opening for Skid Row in North America in February 1992 on that band's "Slave to the Grind" tour. Soundgarden then headed to Europe for a month-long headlining theater tour before returning to tour in the United States. They rejoined Guns N' Roses and the Use Your Illusion Tour in the summer of 1992 for a tour of Europe along with fellow opening act Faith No More. Regarding the time spent opening for Guns N' Roses, Cornell said: "It wasn't a whole lot of fun going out in front of 40,000 people for 35 minutes every day. Most of them hadn't heard our songs and didn't care about them. It was a bizarre thing." The band would go on to play the 1992 Lollapalooza tour with the Red Hot Chili Peppers and Pearl Jam, among others. They later released "Motorvision", which was filmed at the Paramount Theatre in 1992.


title: Badmotorfinger

text: In anticipation of the band's appearance on the 1992 Lollapalooza tour, a limited edition of "Badmotorfinger" was released on June 28, 1992, with a second disc containing the EP "Satan Oscillate My Metallic Sonatas" (or "SOMMS"). The title is a palindrome. This EP includes three covers, an unreleased original song, and a live version of "Slaves & Bulldozers". For the cover of Black Sabbath's "Into the Void", the original lyrics were replaced with words of protest by Chief Seattle (also known as Sealth), which fit the meter of the song. At the 1993 Grammy Awards, "Into the Void (Sealth)" received a nomination for Best Metal Performance.


title: Badmotorfinger

text: "Satanoscillatemymetallicsonatas" was reissued on purple 12" vinyl for Record Store Day on November 25, 2016.


title: Badmotorfinger

text: "Cold Bitch", which was one of Shepherd's favorite songs the band recorded, was featured on the "Spoonman" single in 1994, while "She's a Politician" appeared on the "Burden in My Hand" single in 1996.


title: Badmotorfinger

text: The song "Birth Ritual" was worked on during the "Badmotorfinger" recording sessions, but was not completed. The finished version would eventually see release on the "Singles" in 1992, and later, on both the "Telephantasm" (2010) and "" (2014) compilations.


title: Badmotorfinger

text: "No Attention", which later appeared on the band's 1996 album, "Down on the Upside", was attempted during the recording sessions, but "did not work" according to Kim Thayil.


title: Badmotorfinger

text: "Black Rain" was mostly recorded during the sessions, but the vocals were never completed. It was eventually finished in 2010 and released on "Telephantasm" and "Echo of Miles: Scattered Tracks Across The Path".


title: Badmotorfinger

text: Three tracks were discarded during the mixing process, two of which were "A Broom", and "How Should I Know?"


title: Badmotorfinger

text: Although "Badmotorfinger"s singles featured plenty of B-sides, none of these were from the recording sessions for the album. A one-day recording session with Stuart Hallerman yielded "Stray Cat Blues", "Into the Void (Sealth)", "Girl U Want", "Show Me", and "Touch Me". "Show Me" was later featured on the 1993 "No Alternative" compilation, and "Girl U Want" was later featured on the "Fell on Black Days" single.


title: Badmotorfinger

text: The information regarding accolades attributed to "Badmotorfinger" is adapted in part from AcclaimedMusic.net.


title: Pearson's chi-squared test

text: Pearson's chi-squared test (formula_1) is a statistical test applied to sets of categorical data to evaluate how likely it is that any observed difference between the sets arose by chance. It is the most widely used of many chi-squared tests (e.g., Yates, likelihood ratio, portmanteau test in time series, etc.) – statistical procedures whose results are evaluated by reference to the chi-squared distribution. Its properties were first investigated by Karl Pearson in 1900. In contexts where it is important to improve a distinction between the test statistic and its distribution, names similar to "Pearson χ-squared" test or statistic are used.


title: Pearson's chi-squared test

text: It tests a null hypothesis stating that the frequency distribution of certain events observed in a sample is consistent with a particular theoretical distribution. The events considered must be mutually exclusive and have total probability 1. A common case for this is where the events each cover an outcome of a categorical variable.


title: Pearson's chi-squared test

text: A simple example is the hypothesis that an ordinary six-sided is "fair" (i. e., all six outcomes are equally likely to occur.)


title: Pearson's chi-squared test

text: Pearson's chi-squared test is used to assess three types of comparison: goodness of fit, homogeneity, and independence.


title: Pearson's chi-squared test

text: In this case formula_10 observations are divided among formula_11 cells. A simple application is to test the hypothesis that, in the general population, values would occur in each cell with equal frequency. The "theoretical frequency" for any cell (under the null hypothesis of a discrete uniform distribution) is thus calculated as


title: Pearson's chi-squared test

text: and the reduction in the degrees of freedom is formula_13, notionally because the observed frequencies formula_14 are constrained to sum to formula_10.


title: Pearson's chi-squared test

text: When testing whether observations are random variables whose distribution belongs to a given family of distributions, the "theoretical frequencies" are calculated using a distribution from that family fitted in some standard way. The reduction in the degrees of freedom is calculated as formula_16, where formula_17 is the number of parameters used in fitting the distribution. For instance, when checking a three-parameter Generalized gamma distribution, formula_18, and when checking a normal distribution (where the parameters are mean and standard deviation), formula_19, and when checking a Poisson distribution (where the parameter is the expected value), formula_20. Thus, there will be formula_21 degrees of freedom, where formula_11 is the number of categories.


title: Pearson's chi-squared test

text: The degrees of freedom are not based on the number of observations as with a Student's t or F-distribution. For example, if testing for a fair, six-sided , there would be five degrees of freedom because there are six categories or parameters (each number); the number of times the die is rolled does not influence the number of degrees of freedom.


title: Pearson's chi-squared test

text: The chi-squared statistic can then be used to calculate a p-value by comparing the value of the statistic to a chi-squared distribution. The number of degrees of freedom is equal to the number of cells formula_11, minus the reduction in degrees of freedom, formula_32.


title: Pearson's chi-squared test

text: The result about the numbers of degrees of freedom is valid when the original data are multinomial and hence the estimated parameters are efficient for minimizing the chi-squared statistic. More generally however, when maximum likelihood estimation does not coincide with minimum chi-squared estimation, the distribution will lie somewhere between a chi-squared distribution with formula_33 and formula_34 degrees of freedom (See for instance Chernoff and Lehmann, 1954).


title: Pearson's chi-squared test

text: In Bayesian statistics, one would instead use a Dirichlet distribution as conjugate prior. If one took a uniform prior, then the maximum likelihood estimate for the population probability is the observed probability, and one may compute a credible region around this or another estimate.


title: Pearson's chi-squared test

text: In this case, an "observation" consists of the values of two outcomes and the null hypothesis is that the occurrence of these outcomes is statistically independent. Each observation is allocated to one cell of a two-dimensional array of cells (called a contingency table) according to the values of the two outcomes. If there are "r" rows and "c" columns in the table, the "theoretical frequency" for a cell, given the hypothesis of independence, is


title: Pearson's chi-squared test

text: is the fraction of observations of type "i" ignoring the column attribute (fraction of row totals), and


title: Pearson's chi-squared test

text: is the fraction of observations of type "j" ignoring the row attribute (fraction of column totals). The term "frequencies" refers to absolute numbers rather than already normalized values.


title: Pearson's chi-squared test

text: Note that formula_41 is 0 if and only if formula_42, i.e. only if the expected and true number of observations are equal in all cells.


title: Pearson's chi-squared test

text: Fitting the model of "independence" reduces the number of degrees of freedom by "p" = "r" + "c" − 1. The number of degrees of freedom is equal to the number of cells "rc", minus the reduction in degrees of freedom, "p", which reduces to ("r" − 1)("c" − 1).


title: Pearson's chi-squared test

text: For the test of independence, also known as the test of homogeneity, a chi-squared probability of less than or equal to 0.05 (or the chi-squared statistic being at or larger than the 0.05 critical point) is commonly interpreted by applied workers as justification for rejecting the null hypothesis that the row variable is independent of the column variable.


title: Pearson's chi-squared test

text: The alternative hypothesis corresponds to the variables having an association or relationship where the structure of this relationship is not specified.


title: Pearson's chi-squared test

text: The chi-squared test, when used with the standard approximation that a chi-squared distribution is applicable, has the following assumptions:


title: Pearson's chi-squared test

text: A test that relies on different assumptions is Fisher's exact test; if its assumption of fixed marginal distributions is met it is substantially more accurate in obtaining a significance level, especially with few observations. In the vast majority of applications this assumption will not be met, and Fisher's exact test will be over conservative and not have correct coverage.


title: Pearson's chi-squared test

text: The null distribution of the Pearson statistic with "j" rows and "k" columns is approximated by the chi-squared distribution with


title: Pearson's chi-squared test

text: This approximation arises as the true distribution, under the null hypothesis, if the expected value is given by a multinomial distribution. For large sample sizes, the central limit theorem says this distribution tends toward a certain multivariate normal distribution.


title: Pearson's chi-squared test

text: In the special case where there are only two cells in the table, the expected values follow a binomial distribution,


title: Pearson's chi-squared test

text: In the above example the hypothesised probability of a male observation is 0.5, with 100 samples. Thus we expect to observe 50 males.


title: Pearson's chi-squared test

text: If "n" is sufficiently large, the above binomial distribution may be approximated by a Gaussian (normal) distribution and thus the Pearson test statistic approximates a chi-squared distribution,


title: Pearson's chi-squared test

text: Let "O" be the number of observations from the sample that are in the first cell. The Pearson test statistic can be expressed as


title: Pearson's chi-squared test

text: By the normal approximation to a binomial this is the squared of one standard normal variate, and hence is distributed as chi-squared with 1 degree of freedom. Note that the denominator is one standard deviation of the Gaussian approximation, so can be written


title: Pearson's chi-squared test

text: So as consistent with the meaning of the chi-squared distribution, we are measuring how probable the observed number of standard deviations away from the mean is under the Gaussian approximation (which is a good approximation for large "n").


title: Pearson's chi-squared test

text: The chi-squared distribution is then integrated on the right of the statistic value to obtain the P-value, which is equal to the probability of getting a statistic equal or bigger than the observed one, assuming the null hypothesis.


title: Pearson's chi-squared test

text: When the test is applied to a contingency table containing two rows and two columns, the test is equivalent to a Z-test of proportions.


title: Pearson's chi-squared test

text: Broadly similar arguments as above lead to the desired result, though the details are more involved. One may apply an orthogonal change of variables to turn the limiting summands in the test statistic into one fewer squares of i.i.d. standard normal random variables.


title: Pearson's chi-squared test

text: Let us now prove that the distribution indeed approaches asymptotically the formula_1 distribution as the number of observations approaches infinity.


title: Pearson's chi-squared test

text: Let formula_11 be the number of observations, formula_50 the number of cells and formula_51 the probability of an observation to fall in the i-th cell, for formula_52. We denote by formula_53 the configuration where for each i there are formula_54 observations in the i-th cell. Note that


title: Pearson's chi-squared test

text: Let formula_56 be Pearson's cumulative test statistic for such a configuration, and let formula_57 be the distribution of this statistic. We will show that the latter probability approaches the formula_1 distribution with formula_59 degrees of freedom, as formula_60


title: Pearson's chi-squared test

text: We will use a procedure similar to the approximation in de Moivre–Laplace theorem. Contributions from small formula_54 are of subleading order in formula_11 and thus for large formula_11 we may use Stirling's formula for both formula_65 and formula_66 to get the following:


title: Pearson's chi-squared test

text: we may approximate for large formula_11 the sum over the formula_54 by an integral over the formula_71. Noting that:


title: Pearson's chi-squared test

text: Pearson's chi, formula_76, is precisely the argument of the exponent (except for the -1/2; note that the final term in the exponent's argument is equal to formula_77).


title: Pearson's chi-squared test

text: formula_79 is a regular symmetric formula_80 matrix, and hence diagonalizable. It is therefore possible to make a linear change of variables in formula_81 so as to get formula_59 new variables formula_83 so that:


title: Pearson's chi-squared test

text: This is the probability that squared sum of formula_59 independent normally distributed variables of zero mean and unit variance will be greater than T, namely that formula_1 with formula_59 degrees of freedom is larger than T.


title: Pearson's chi-squared test

text: We have thus shown that at the limit where formula_89 the distribution of Pearson's chi approaches the chi distribution with formula_59 degrees of freedom.


title: Pearson's chi-squared test

text: A 6-sided die is thrown 60 times. The number of times it lands with 1, 2, 3, 4, 5 and 6 face up is 5, 8, 9, 8, 10 and 20, respectively. Is the die biased, according to the Pearson's chi-squared test at a significance level of 95% and/or 99%?


title: Pearson's chi-squared test

text: The null hypothesis is that the die is unbiased, hence each number is expected to occur the same number of times, in this case, = 10. The outcomes can be tabulated as follows:


title: Pearson's chi-squared test

text: We then consult an "Upper-tail critical values of chi-square distribution" table. There the tabular value refers to the sum (not the average) of the given number (N=60 trials) of squared Normal variables, so 13.4 is the experimental result whose unlikeliness (with a fair die) we wish to estimate.


title: Pearson's chi-squared test

text: The experimental sum of 13.4 is between the critical values of 97.5% and 99% significance or confidence (p-value). Specifically, getting 20 rolls of 6, when the expectation is only 10 such values, is unlikely with a fair die.


title: Pearson's chi-squared test

text: In this context, the frequencies of both theoretical and empirical distributions are unnormalised counts, and for a chi-squared test the total sample sizes formula_10 of both these distributions (sums of all cells of the corresponding contingency tables) have to be the same.


title: Pearson's chi-squared test

text: For example, to test the hypothesis that a random sample of 100 people has been drawn from a population in which men and women are equal in frequency, the observed number of men and women would be compared to the theoretical frequencies of 50 men and 50 women. If there were 44 men in the sample and 56 women, then


title: Pearson's chi-squared test

text: If the null hypothesis is true (i.e., men and women are chosen with equal probability), the test statistic will be drawn from a chi-squared distribution with one degree of freedom (because if the male frequency is known, then the female frequency is determined).


title: Pearson's chi-squared test

text: Consultation of the chi-squared distribution for 1 degree of freedom shows that the probability of observing this difference (or a more extreme difference than this) if men and women are equally numerous in the population is approximately 0.23. This probability is higher than conventional criteria for statistical significance (0.01 or 0.05), so normally we would not reject the null hypothesis that the number of men in the population is the same as the number of women (i.e., we would consider our sample within the range of what we would expect for a 50/50 male/female ratio.)


title: Pearson's chi-squared test

text: The approximation to the chi-squared distribution breaks down if expected frequencies are too low. It will normally be acceptable so long as no more than 20% of the events have expected frequencies below 5. Where there is only 1 degree of freedom, the approximation is not reliable if expected frequencies are below 10. In this case, a better approximation can be obtained by reducing the absolute value of each difference between observed and expected frequencies by 0.5 before squaring; this is called Yates's correction for continuity.


title: Pearson's chi-squared test

text: In cases where the expected value, E, is found to be small (indicating a small underlying population probability, and/or a small number of observations), the normal approximation of the multinomial distribution can fail, and in such cases it is found to be more appropriate to use the G-test, a likelihood ratio-based test statistic. When the total sample size is small, it is necessary to use an appropriate exact test, typically either the binomial test or, for contingency tables, Fisher's exact test. This test uses the conditional distribution of the test statistic given the marginal totals, and thus assumes that the margins were determined before the study; alternatives such as Boschloo's test which do not make this assumption are uniformly more powerful.


title: Pearson's chi-squared test

text: It can be shown that the formula_1 test is a low order approximation of the formula_94 test. The above reasons for the above issues become apparent when the higher order terms are investigated.


title: Abigail Spanberger

text: Abigail Anne Spanberger (née Davis, August 7, 1979) is an American politician serving as the U.S. representative from since 2019. She is a member of the Democratic Party. Her district includes most of the northern suburbs of Richmond, as well as some exurban territory around Fredericksburg. Spanberger is a former Central Intelligence Agency (CIA) officer.


title: Abigail Spanberger

text: Spanberger defeated Republican incumbent Dave Brat in 2018, ending the Republican Party's 36-year hold on the district. She won reelection in 2020 and 2022.


title: Abigail Spanberger

text: Abigail Spanberger was born in Red Bank, New Jersey, on August 7, 1979. When she was 13, her family relocated to the Short Pump area in Henrico County in Virginia, outside Richmond. She attended John Randolph Tucker High School. Spanberger was later a page for U.S. Senator Chuck Robb.


title: Abigail Spanberger

text: Spanberger earned a Bachelor of Arts degree from the University of Virginia and a Master of Business Administration from a joint program between the GISMA Business School in Germany and Purdue University's Krannert School of Management.


title: Abigail Spanberger

text: In 2002 and 2003, Spanberger taught English literature as a substitute teacher at the Islamic Saudi Academy in Northern Virginia. In the early 2000s, she was a postal inspector, working on money laundering and narcotics cases.


title: Abigail Spanberger

text: In 2006, Spanberger joined the Central Intelligence Agency as an operations officer. She said she gathered intelligence about nuclear proliferation and terrorism.


title: Abigail Spanberger

text: In 2014, Spanberger left the CIA and entered the private sector. She was hired by Royall & Company (now EAB). In 2017, Virginia Governor Terry McAuliffe appointed her to the Virginia Fair Housing Board.


title: Abigail Spanberger

text: In July 2017, Spanberger announced her candidacy for the United States House of Representatives in in the 2018 election against incumbent Republican Dave Brat, a Tea Party movement member. She made the final decision to run after the House of Representatives voted to repeal the Affordable Care Act. On June 12, 2018, Spanberger defeated Dan Ward in the Democratic primary election with 73% of the vote, receiving more votes than any other candidate in the Virginia primaries that day. Her campaign outraised Brat's.


title: Abigail Spanberger

text: In August, the Congressional Leadership Fund, a super PAC closely aligned with Republican Speaker of the House Paul Ryan, conducted a smear campaign against Spanberger. The smear campaign, which attempted to tie her to terrorism, was based on an SF-86 application she completed to obtain security clearance, which was inappropriately released in breach of privacy rules. She won the November 6 general election by just over 6,600 votes. While Brat won eight of the district's ten counties, Spanberger dominated the two largest counties, Henrico and Chesterfield, by a combined margin of over 30,000 votes.


title: Abigail Spanberger

text: In a visit to the district, former Trump adviser Steve Bannon described it as "an absolute bellwether of the entire country", adding that losing the district would mean the GOP losing control of the House.


title: Abigail Spanberger

text: A number of sources claimed Spanberger was the first Democrat to win this seat since 1970, when four-term Democrat John Marsh retired and was succeeded by Republican J. Kenneth Robinson. But until 1993, the 7th stretched from the outer Washington suburbs through the Shenandoah Valley and Charlottesville to the outer Richmond suburbs; the present 7th is geographically and demographically the successor to what was the 3rd district before 1993.


title: Abigail Spanberger

text: Spanberger faced a close reelection contest against State Delegate Nick Freitas, who represents much of the congressional district's northern portion. She won with 51% of the vote to Freitas's 49%. Freitas carried eight of the district's ten counties, as Brat had done two years earlier. But Spanberger again prevailed by winning the district's shares of Henrico and Chesterfield counties by a combined 43,400 votes, five times her overall margin of 8,400 votes. She was also boosted by Joe Biden narrowly carrying the district; Biden is the first Democrat to win what is now the 7th since 1948.